如题,我的代码
#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
求大佬看看