90求助有详细注释,标准版已过
查看原帖
90求助有详细注释,标准版已过
467107
Cap1taL楼主2021/10/5 00:33

如题,我的代码

#include <iostream>			
#include <queue>		
#include <vector>		
#define MAXN 100005		
using namespace std;
struct Node{
    int id,d;
    bool operator < (const Node x)const{return d>x.d;}
};
int n,m,s,dis[MAXN],vis[MAXN],in1,in2,in3;
vector <Node> edge[MAXN];
priority_queue <Node> q;	
void dijkstra(int s){		
    for(int i=1;i<=n;i++)   dis[i]=0x3f3f3f3f;		
    dis[s]=0;	
    q.push((Node){s,0});	
    while(!q.empty()){		
        Node now=q.top(); q.pop();	
        if(vis[now.id]) continue;	
        vis[now.id]=1;				
        for(int i=0;i<edge[now.id].size();i++)
            if(dis[edge[now.id][i].id] > now.d + edge[now.id][i].d)
				q.push( (Node) {edge[now.id][i].id , dis[edge[now.id][i].id]=now.d+edge[now.id][i].d} );  
    }
}
int main(){
    cin>>n>>m>>s;	
    for(int i=1;i<=m;i++){	
        cin>>in1>>in2>>in3;	
        edge[in1].push_back((Node){in2,in3});
    }
    dijkstra(s);
    for(int i=1;i<=n;i++)   cout<<dis[i]<<' ';
    return 0;
}

详细的注释在https://www.luogu.com.cn/blog/XHZS-XY/dijkstra-mu-ban

测试点是这个 03.in

5 15 5
2 2 270
1 4 89
2 1 3
5 5 261
5 2 163
5 5 275
4 5 108
4 4 231
3 4 213
3 3 119
3 1 77
3 1 6
2 4 83
5 5 196
5 5 94

03.out

166 163 2147483647 246 0 

我的输出

166 163 1061109567 246 0

求大佬看看

2021/10/5 00:33
加载中...