1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int M = 1e6 + 5;
 4 vector< int >f[M];
 5 queue<int>Q;
 6 bool vis[M];//全局变量一开始全部为0
 7 void dfs(int x)
 8 {
 9     cout << x << " ";
10     for (int i = 0; i < f[x].size(); i++)
11     {
12         int next = f[x][i];
13         if (!vis[next])
14         {
15             vis[next] = true;
16             dfs(next);
17         }
18     }
19 }
20 int main()
21 {
22     int n, m;
23     cin >> n >> m;
24     for (int i = 0; i < m; i++)
25     {
26         int x, y;
27         cin >> x >> y;
28         f[x].push_back(y);
29     }
30     for (int i = 0; i < m; i++)
31     {
32         sort(f[i].begin(), f[i].end());
33     }
34     vis[1] = 1;
35     dfs(1);
36     cout << endl;
37     memset(vis, 0, sizeof(vis));//重新初始化
38     Q.push(1); vis[1] = 1;//bfs
39     while (!Q.empty())
40     {
41         int X = Q.front(); Q.pop();
42         cout << X << " ";
43         for (int i = 0; i < f[X].size(); i++)
44         {
45             int next = f[X][i];
46             if (!vis[next])
47             {
48                 vis[next]=1;
49                 Q.push(next);
50             }
51         }
52     }
53     return 0;
54 }

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 const ll INF = 1e9 + 10, MOD = 998244354,M=505;
 5 ll f[M][M];
 6 int main()
 7 {
 8     int n, m;
 9     cin >> n >> m;
10     /*memset(f, INF, sizeof(f));不建议使用，其实和遍历时间复杂度一样*/
11     for (int i = 1; i <= n; i++)
12     {
13         for (int j = 1; j <= n; j++) {
14             if (i == j)f[i][j] == 0;
15             else
16             {
17                 f[i][j] = INF;//赋初值
18             }
19             
20         }
21     }
22      
23     for (int i = 1; i <= m; i++)
24     {
25         ll x, y, l;
26         cin >> x >> y >> l;
27         f[x][y] = min(l,f[x][y]);
28         f[y][x] = min(l, f[y][x]);//有重复的路径但是路程不同取最短路程
29     }
30  
31     for (int k = 1; k <= n; k++)
32     {
33         for (int i = 1; i <= n; i++)
34         {
35             for (int j = 1; j <= n; j++)
36             {
37                 f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
38             }
39         }
40     }
41     for (int i = 1; i <= n; i++) {
42         ll sum = 0;
43         for (int j = 1; j <= n; j++) {
44             sum = (sum + f[i][j]) % MOD;
45         }
46         cout << sum << endl;
47     }
48     return 0;
49 }

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 1e5 + 50, INF = 1e9 + 1000,maxm=5e5+50;
 4 struct edge
 5 {
 6     int next;//同一个起点的上一个点
 7     int to;//终点
 8     int dis;//权值
 9 };
10 edge e[maxm];
11 int ans[maxn];
12 bool vis[maxn];
13 int head[maxn],tot;
14 inline void add_edge(int st, int ed, int dis)//链式前向星的模板
15 {
16     e[++tot].dis = dis;
17     e[tot].to = ed;
18     e[tot].next = head[st];
19     head[st] = tot;
20 }
21 struct node
22 {
23     int now;
24     int dis;
25     bool operator < (const node& x)const
26     {
27         return x.dis < dis;
28     }
29 };
30 priority_queue<node>Q;//由小到大
31 int main()
32 {
33     int n, m, s;
34     cin >> n >> m >> s;
35     for (int i = 1; i <= n; i++)ans[i] = INF;
36     ans[s] = 0;
37     for (int i = 0; i < m; i++)
38     {
39         int u, v, w;
40         cin >> u >> v >> w;
41         add_edge(u, v, w);
42     }
43     Q.push({ s,0 });
44     while (!Q.empty())//dijkstra模板
45     {
46         auto X = Q.top();
47         Q.pop();
48         int now = X.now;
49         if (vis[now])continue;
50         vis[now] = 1;
51         for (int i = head[now]; i; i = e[i].next)//链式前向星遍历模板
52         {
53             int Y = e[i].to;
54             if (ans[Y] > ans[now] + e[i].dis)
55             {
56                 ans[Y] = ans[now] + e[i].dis;
57                 if (!vis[Y])
58                 {
59                     Q.push({ Y, ans[Y] });
60                 }
61             }
62         }
63     }
64     for (int i = 1; i <= n; i++)
65     {
66         cout << ans[i] << " ";
67     }
68     return 0;
69 }