P3371 【模板】单源最短路径（弱化版）

天天吹这题模板题那题模板题，这题还真tm是道模板题。。

既然模板题咱就不多说了，放上两种最短路的基本做法

邻接表+spfa：

 1 const long long inf=2147483647;
 2 const int maxn=10005;
 3 const int maxm=500005;
 4 using namespace std;
 5 int n,m,s,num_edge=0;
 6 int dis[maxn],vis[maxn],head[maxm];
 7 struct Edge{
 8     int next,to,dis;
 9 }edge[maxm];
10 void addedge(int from,int to,int dis){
11     edge[++num_edge].next=head[from];
12     edge[num_edge].to=to;
13     edge[num_edge].dis=dis;
14     head[from]=num_edge;
15 }
16 void spfa(){
17     queue<int> q;
18     for(int i=1; i<=n; i++) {
19         dis[i]=inf;
20         vis[i]=0;
21     }
22     q.push(s); dis[s]=0; vis[s]=1;
23     while(!q.empty()){
24         int u=q.front();
25         q.pop();
26         vis[u]=0;
27         for(int i=head[u];i;i=edge[i].next){
28             int v=edge[i].to; 
29             if(dis[v]>dis[u]+edge[i].dis){
30                 dis[v]=dis[u]+edge[i].dis;
31                 if(vis[v]==0){
32                     vis[v]=1;
33                     q.push(v);
34                 }
35               }
36         }
37     }
38 }
39 int main(){
40     scanf("%d%d%d",&n,&m,&s);
41     for(int i=1; i<=m; i++){
42         int f,g,w;
43         scanf("%d%d%d",&f,&g,&w);
44         addedge(f,g,w);
45     }
46     spfa();
47     for(int i=1;i<=n;i++){
48         if(s==i){
49             printf("0 ");
50         }
51         else{
52             printf("%d ",dis[i]);
53         }
54     }
55     return 0;
56 }

链式前向星+Dijkstra

 1 struct Edge{
 2     int u,v,w,next;
 3 }e[maxm];
 4 int head[maxn],cnt,n,m,s,vis[maxn],dis[maxn];
 5 struct node{
 6     int w,now;
 7     bool operator <(const node &x)const{
 8         return w>x.w;
 9     }
10 };
11 priority_queue<node>q;
12 inline void add(int u,int v,int w){
13     e[++cnt].u=u;
14     e[cnt].v=v;
15     e[cnt].w=w;
16     e[cnt].next=head[u];
17     head[u]=cnt;
18 }
19 void dijkstra(){
20     for(int i=1;i<=n;i++){
21         dis[i]=INF;
22     }
23     dis[s]=0;
24     q.push((node){0,s});
25     while(!q.empty()){
26         node x=q.top();
27         q.pop();
28         int u=x.now;
29         if(vis[u]) continue; 
30         vis[u]=1;
31         for(int i=head[u];i;i=e[i].next){
32             int v=e[i].v;
33             if(dis[v]>dis[u]+e[i].w){
34                 dis[v]=dis[u]+e[i].w;
35                 q.push((node){dis[v],v});
36             }
37         }
38     }
39 }
40 int main(){
41     scanf("%d%d%d",&n,&m,&s);
42     for(int i=1,x,y,z;i<=m;i++){
43         scanf("%d%d%d",&x,&y,&z);
44         add(x,y,z);
45     }
46     dijkstra();
47     for(int i=1;i<=n;i++){
48         printf("%d ",dis[i]);
49     }
50     return 0;
51 }

嗯就这样了，某人睡觉了，我也要睡觉了嘻嘻，晚安