LOJ #119 最短路(模板)

背景

LOJ 上的模板題，閑來無事&複習noip用各種做法開始寫，一晚上能寫完吧。。。。

題目

#119. 最短路 -LibreOJ

題解

暴力（DFS）

期望得分：30

實際得分：30

複雜度： (約為指數級複雜度)

代碼：

#include <bits/stdc++.h>nusing namespace std;nconst int INF = 1 << 30;nint n, m, s, t;nint road[2505][2505];nint ans = INF, tmp = 0;nint vis[2505];nn// 暴力dfs版本nnint read()n{n int x = 0;n char c = getchar();n while (c < 0 || c > 9) c = getchar();n while (c >= 0 && c <= 9) x = x * 10 + c - 0, c = getchar();n return x;n}nnvoid dfs(int cur)n{n if (cur == t)n {n if (tmp < ans) ans = tmp;n return;n }n for (int i = 1; i <= n; ++i)n {n if (road[cur][i] == 0) continue;n if (vis[i] == 1) continue;n tmp += road[cur][i];n vis[i] = 1;n dfs(i);n tmp -= road[cur][i];n vis[i] = 0;n }n return;n}nnint main()n{n memset(road, 0, sizeof(road));n memset(vis, 0, sizeof(vis));n n = read();n m = read();n s = read();n t = read();n for (int i = 1; i <= m; ++i)n {n int a, b;n a = read();n b = read();n road[a][b] = read();n road[b][a] = road[a][b];n }n vis[s] = 1;n dfs(s);n printf("%d", ans);n return 0;n}n

Floyd-Warshall(後面那個詞是這麼拼寫吧。。)

期望得分：70

實際得分：70

時間複雜度：

代碼：

#include <bits/stdc++.h>nusing namespace std;nconst int INF = (1 << 30) - 1;nint n, m, s, t;nint road[2505][2505];nn// floyd的O(n^3)nnint read()n{n int x = 0;n char c = getchar();n while (c < 0 || c > 9) c = getchar();n while (c >= 0 && c <= 9) x = x * 10 + c - 0, c = getchar();n return x;n}nnvoid floyd()n{n for (int i = 1;i <= n;i++)n for (int j = 1;j <= n;j++)n for (int k = 1;k <= n;k++)n {n road[j][k] = min(road[j][k], road[j][i] + road[i][k]);n road[k][j] = road[j][k];n }n}nnint main()n{n n = read();n m = read();n s = read();n t = read();n for (int i = 1; i <= n; ++i)n for (int j = 1; j <= n; ++j)n road[i][j] = INF;n for (int i = 1; i <= m; ++i)n {n int a, b;n a = read();n b = read();n road[a][b] = read();n road[b][a] = road[a][b];n }n floyd();n printf("%d", road[s][t]);n return 0;n}n

以下待填坑

Dijkstra

期望得分：100

實際得分：不知道。。

Bellman-Ford

期望得分：100

實際得分：不知道。。

SPFA

期望得分：100

實際得分：不知道。。

最小生成樹