Dijkstra（n^2版）

 1 #define IO std::ios::sync_with_stdio(0)
 2 #include <bits/stdc++.h>
 3 #define pb push_back
 4 using namespace std;
 5 typedef long long ll;
 6 const int N=1005;
 7 struct node{
 8     int x;
 9     int dis;
10 };
11 const int Maxv=2147483647;
12 vector<node>G[N];
13 int n,m,s;
14 int d[N];
15 int vis[N];
16 void dijkstra(){
17     fill(d+1,d+1+n,Maxv);//不能用memset，巨坑
18     d[s]=0;
19     for(int i=1;i<=n;i++){
20         int u=-1;
21         int mi=Maxv;
22         for(int j=1;j<=n;j++){
23             if(!vis[j]&&d[j]<mi){
24                 mi=d[j];
25                 u=j;
26             }
27         }
28         if(u==-1)return;
29         vis[u]=1;
30         for(int j=0;j<G[u].size();j++){
31             int v=G[u][j].x;
32             if(!vis[v]){
33                 int dis=G[u][j].dis;
34                 if(d[u]+dis<d[v])d[v]=d[u]+dis;
35             }
36         }
37     }
38 }
39 
40 int main(){
41     IO;
42     cin>>n>>m>>s;
43     for(int i=1;i<=m;i++){
44         int u,v,w;
45         cin>>u>>v>>w;
46         G[u].pb((node){v,w});
47     }
48     dijkstra();
49     for(int i=1;i<=n;i++)cout<<d[i]<<" ";
50 
51 }
52 
53 /*
54 
55 4 6 1
56 1 2 2
57 2 3 2
58 2 4 1
59 1 3 5
60 3 4 3
61 1 4 4
62 
63 */