P4779 【模板】单源最短路径（标准版）

 1 #include<set>
 2 #include<map>
 3 #include<list>
 4 #include<queue>
 5 #include<stack>
 6 #include<string>
 7 #include<cmath>
 8 #include<ctime>
 9 #include<vector>
10 #include<bitset>
11 #include<memory>
12 #include<utility>
13 #include<cstdio>
14 #include<sstream>
15 #include<iostream>
16 #include<cstdlib>
17 #include<cstring>
18 #include<algorithm>
19 using namespace std;
20 
21 inline int get(){//快读
22     char c=getchar();
23     int res=0;
24     while (c<‘0‘||c>‘9‘) c=getchar();
25     while (c>=‘0‘&&c<=‘9‘){
26         res=(res<<3)+(res<<1)+c-‘0‘;
27         c=getchar();
28     }
29     return res;
30 }
31 
32 struct edge{
33     int to, dis, next;
34 };
35 int n,m,s,tot;
36 edge e[500005];
37 int head[100005],dis[100005];
38 bool vis[100005];
39 struct node{
40     int dis;
41     int id;
42     bool operator <(const node &x)const{//重构的另一种写法
43         return x.dis<dis;
44     }
45 };
46 priority_queue<node> q;//堆优化
47 
48 inline void add(int u,int v,int d){//链式前向星
49     tot++;
50     e[tot].dis=d;
51     e[tot].to=v;
52     e[tot].next=head[u];
53     head[u]=tot;
54 }
55 
56 inline void dijkstra(){//最短路嘤嘤嘤
57     dis[s]=0;
58     q.push((node){0,s});
59     while(!q.empty()){
60         node t=q.top();
61         q.pop();
62         int x=t.id,d=t.dis;
63         if(vis[x])continue;
64         vis[x]=1;
65         for(int i=head[x];i;i=e[i].next){
66             int y=e[i].to;
67             if( dis[y]>dis[x]+e[i].dis){
68                 dis[y]=dis[x]+e[i].dis;
69                 if(!vis[y]){
70                     q.push((node){dis[y],y});
71                 }
72             }
73         }
74     }
75 }
76 
77 int main(){
78     n=get();m=get();s=get();
79     memset(dis,0x3f,sizeof(dis));//初始化
80     for(register int i=0,u,v,w;i<m;i++){
81         u=get();v=get();w=get();
82         add(u,v,w);
83     }
84     dijkstra();
85     for(int i=1;i<=n;i++){
86         printf("%d ",dis[i]);
87     }
88     return 0;
89 }