P4779 【模板】单源最短路径（标准版）/ vv123的代码规范

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,m,s,u,v,w,head[100005],d[100005],cnt;
 4 bool vis[100005];
 5 
 6 struct Edge{
 7     int v,w,next;
 8 }e[500005];
 9 
10 struct Node{
11     int w,pos;
12     bool operator < (const Node &x) const{
13       return x.w<w;
14     }
15 };
16 
17 void add(int u,int v,int w){
18     e[++cnt].v=v;
19     e[cnt].w=w;
20     e[cnt].next=head[u];
21     head[u]=cnt;
22 }
23 
24 void dijkstra(){
25     d[s]=0;
26     priority_queue<Node> q;
27     q.push((Node){0,s});
28     
29     while(!q.empty()){
30         Node t=q.top();q.pop();
31         int u=t.pos,w=t.w;
32         if(vis[u])continue;
33         vis[u]=true;
34         
35         for(int i=head[u];i;i=e[i].next){
36             int v=e[i].v;
37             if(d[v]>d[u]+e[i].w){
38                 d[v]=d[u]+e[i].w;
39                 if(!vis[v])q.push((Node){d[v],v});
40             }
41         }
42   }
43 }
44 
45 int main(){
46     ios::sync_with_stdio(false);
47     memset(d,127,sizeof(d));
48     cin>>n>>m>>s;
49     for(int i=1;i<=m;i++){
50         cin>>u>>v>>w;
51         add(u,v,w);
52     }
53     dijkstra();
54     for(int i=1;i<=n;i++)
55       cout<<d[i]<<" ";
56 }