社区讨论

为什么优先队列cmp wa 1 3 4 ????qwq

P4779【模板】单源最短路径(标准版)参与者 4已保存回复 6

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@mi6x0iz5
此快照首次捕获于
2025/11/20 12:12
4 个月前
此快照最后确认于
2025/11/20 12:12
4 个月前
查看原帖
CPP
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define N 100050
#define int long long
using namespace std;
int n,m,a,b;
int head[N],now=1;
int dis[N];
bool vis[N];
struct wfq{
    int nxt,to,v;
}bian[20000050];
void Add(int x,int y,int z)
{
    bian[now].to=y;
    bian[now].nxt=head[x];
    bian[now].v=z;
    head[x]=now;
    now++;
    return;
}
struct cmp{
    bool operator()(int a,int b){
        return dis[a]>dis[b];
    }
};
void dijkistra(int s)
{
    priority_queue<int,vector<int>,cmp>q;
    rep(i,1,n)dis[i]=2147483647;dis[s]=0;
    q.push(s);
    while(!q.empty())
    {
        int u=q.top();q.pop();
        vis[u]=1;
        for(int i=head[u];i;i=bian[i].nxt)
        {
            int z=bian[i].to;
            if(dis[z]>dis[u]+bian[i].v)
            dis[z]=dis[u]+bian[i].v;
            if(!vis[z])vis[z]=1,q.push(z);
        }
    }
}
signed main()
{
    cin>>n>>m>>a;
    rep(i,1,m)
    {
        int x,y,v;
        scanf("%lld%lld%lld",&x,&y,&v);
        Add(x,y,v),Add(y,x,v);
    }
    dijkistra(a);
    rep(i,1,n)printf("%lld ",dis[i]);
    return 0;
}

回复

6 条回复,欢迎继续交流。

正在加载回复...