求条

DLDZD @ 2024-10-24 08:07:25

#include<bits/stdc++.h>
#define int long long
#define rr read()
using namespace std;
inline int read(){
    int x=0,f=1; char c=getchar_unlocked();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar_unlocked();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar_unlocked();
    }
    return x*f;
}
void write(int i){
    if(i<0) putchar_unlocked('-'),i=-i ;
    if(i>9) write(i/10) ;
    putchar_unlocked((i%10)|0x30) ;
    return ;
}
struct edge{
    int ver,nxt;
    int edge;
}a[1000001];
int head[1000001],tot;
int d[1000001];
bool v[1000001];
int n=rr,m=rr,s=rr;;
priority_queue<pair<int,int> > q;
void add(int x,int y,int z){
    a[++tot].nxt=head[tot];
    head[x]=tot;
    a[tot].ver=y;
    a[tot].edge=z;
}
void dijkstra(){
    for(int i=0;i<=n;i++) d[i]=2147483647;
    d[s]=0;
    q.push(make_pair(0,s));
    while(!q.empty()){
        int x=q.top().second;
        q.pop();
        if(v[x]) continue;
        v[x]=1;
        for(int i=head[x];i;i=a[i].nxt){
            if(d[a[i].ver]>d[x]+a[i].edge){
                d[a[i].ver]=d[x]+a[i].edge;
                if(!v[a[i].ver]){
                    q.push(make_pair(d[a[i].ver],a[i].ver));
                }
            }
        }
    }
    return ;
}
signed main(){
    for(int i=1;i<=m;i++){
        add(rr,rr,rr);
    }
    dijkstra();
    for(int i=1;i<=n;i++){
        write(d[i]);
        putchar(' ');
    }
    return 0;
}

by qjy1024 @ 2024-10-24 08:12:03

STL里头的优先队列如果用pair<int,int>作为参数是先按第一个元素从大到小排序的，你可以写结构体，实在懒就在makepair函数的第一个元素前面加负号

by SugarKite @ 2024-10-24 08:38:39

priority_queue<pair<int,int> > q;改成 priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q; 应该就好了

by qjy1024 @ 2024-10-24 08:47:16

1，dijstra里头没有v[s]=1. 2，优先队列不对 3，read()是不能直接作为函数参数的，顺序会乱，不信你试试 4，getchar_unlocked()是什么东西？ 最后，向前星我是真不会，不理解为什么时空复杂度都和邻接矩阵一样非要用向前星 代码我给你用邻接矩阵重写了一遍

#include <bits/stdc++.h>
#define int long long
#define rr read()
using namespace std;
inline int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
void write(int i)
{
    if (i < 0)
        putchar('-'), i = -i;
    if (i > 9)
        write(i / 10);
    putchar((i % 10) | 0x30);
    return;
}
// struct node
// {
//     int v,w
// };
const int MAXN =1e5+9;
vector<pair<int,int>>G[MAXN];
int d[MAXN];
bool vis[MAXN];
int n = rr, m = rr, s = rr;
priority_queue<pair<int, int>> q;
void dijkstra()
{
    for (int i = 0; i <= n; i++)
        d[i] = 2147483647;
    d[s] = 0;
    q.push(make_pair(0, s));
    while (!q.empty())
    {
        int u = q.top().second;
        q.pop();
        if (vis[u])
            continue;
        vis[u] = 1;
        for(auto x:G[u])
        {
            int v=x.first,w=x.second;
            if(d[u]+w<d[v])
            {
                d[v] = d[u] + w;
                if (!vis[v])
                {
                    q.push(make_pair(-d[v], v));
                }
            }
        }
    }
    return;
}
signed main()
{
    for (int i = 1; i <= m; i++)
    {
        int u=read(),v=read(),w=read();
        G[u].push_back(make_pair(v,w));
    }
    dijkstra();
    for (int i = 1; i <= n; i++)
    {
        write(d[i]);
        putchar(' ');
    }
    return 0;
}

by Texas_the_Omertosa @ 2024-10-24 12:27:35

#include<bits/stdc++.h>
#define int long long
#define rr read()
using namespace std;
inline int read(){
    int x=0,f=1; char c=getchar_unlocked();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar_unlocked();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar_unlocked();
    }
    return x*f;
}
void write(int i){
    if(i<0) putchar_unlocked('-'),i=-i ;
    if(i>9) write(i/10) ;
    putchar_unlocked((i%10)|0x30) ;
    return ;
}
struct edge{
    int ver,nxt;
    int edge;
}a[1000001];
int head[1000001],tot;
int d[1000001];
bool v[1000001];
int n,m,s;
priority_queue<pair<int,int> > q;
void add(int x,int y,int z){
    a[++tot].nxt=head[x];
    head[x]=tot;
    a[tot].ver=y;
    a[tot].edge=z;
}
void dijkstra(){
    for(int i=0;i<=n;i++) d[i]=2147483647;
    d[s]=0;
    q.push(make_pair(0,s));
    while(!q.empty()){
        int x=q.top().second;
        q.pop();
        if(v[x]) continue;
        v[x]=1;
        for(int i=head[x];i;i=a[i].nxt){
            if(d[a[i].ver]>d[x]+a[i].edge){
                d[a[i].ver]=d[x]+a[i].edge;
                q.push(make_pair(-d[a[i].ver],a[i].ver));
            }
        }
    }
    return ;
}
signed main(){
    n=rr,m=rr,s=rr;
    for(int i=1;i<=m;i++){
    int u=rr,v=rr,w=rr;
        add(u,v,w);
    }
    dijkstra();
    for(int i=1;i<=n;i++){
        write(d[i]);
        putchar(' ');
    }
    return 0;
}

by Texas_the_Omertosa @ 2024-10-24 12:28:31

@Guanlinmsl 布什各门，你要不要听听你自己在说什么

by Texas_the_Omertosa @ 2024-10-24 12:34:13

@DLDZD

错误原因：

1. 大根堆没加负号

2. 你自己好好看看你的链式前向星

3. 参数是函数那么每次调用参数都会执行函数，链式前向星一般不可避免有一个变量调用两次。

by qjy1024 @ 2024-10-24 17:44:08

@Texas_the_Omertosa 好吧我确实一时脑抽，但是他调用函数的方法确实是错误的