求助Dijkstra,WA五个点

P4779 【模板】单源最短路径(标准版)

ForMyDream @ 2022-07-01 09:35:00

#include<bits/stdc++.h>
#define maxn 500005
using namespace std;
struct Edge{
    int u,v,w,next;
}edge[maxn*2]; 
int n,m,cnt,head[maxn*2];//cnt:表示有多少条边 
void add(int u,int v,int w){
    cnt++;
    edge[cnt].u=u;
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt;
}
int dis[maxn],vis[maxn],s=1; //vis[s]=1,表示s是黄点 
struct qnode{
    int v,length;//s---v的长度     
    bool operator <(const qnode &r) const{
        return r.length<length;
    }
}; 

void dijkstra(){//m*logn
//  memset(dis,0x7fffffff,sizeof(dis));
    dis[s]=0;
    priority_queue<qnode> que;//元素:点的编号,和到s的值
    que.push((qnode){s,0});
    //找到入伙的点,用改点去更新其他的dis值 
    while(!que.empty()){
        qnode temp=que.top();//就是距离最短的值 logn
        que.pop(); 
        int u=temp.v;
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=head[u];i;i=edge[i].next){
            //更新相应的s到其他点的最小值 
            int v=edge[i].v;//v==3
            if(vis[v]==0&&dis[v]>dis[u]+edge[i].w){
                dis[v]=dis[u]+edge[i].w;
                que.push( (qnode){v,dis[v]} );
            }           
        }   
    }
} 
int main(){
    cin>>n>>m>>s;
    for(int i = 1; i <= n; ++i)dis[i] = 0x3f3f3f3f;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
    }
    dijkstra(); 
    for(int i=1;i<=n;i++){
        if(dis[i]==0x3f3f3f3f)
            cout<<-1<<' ';
        else
            cout<<dis[i]<<' ';
    }

    return 0;
}

by DrBit @ 2022-07-01 09:51:25

(这题不是单向边吗


by ForMyDream @ 2022-07-01 10:05:06

@DrBit 我太粗心了,已经AC,谢谢大佬


|