最短路三种算法的模板：
1. 弗洛伊德：
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <string> #include <map> #include <queue> #include <algorithm> #include <iostream> using namespace std; typedef long long LL;
int G[10][10]; int i, j, k, n, m, x, y;
int main() { cin >> n >> m; for(i = 1; i <= n; i++) { for(j = 1; j <= n; j++) G[i][j] = 1 << 10; } for(i = 1; i <= m; i++) { cin >> x >> y >> k; G[x][y] = k; G[y][x] = k; } for(i = 1; i <= n; i++) { for(j = 1; j <= n; j++) { for(k = 1; k <= n; k++) { if(i == j || i == k || j == k) continue; G[j][k] = min(G[j][k], G[j][i] + G[i][k]); } } } cout << G[1][2] << endl; return 0; }
对应题目：POJ3660、POJ3615
POJ - 3660题解：
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <string> #include <map> #include <queue> #include <iostream> #include <algorithm> using namespace std; typedef long long ll;
int G[107][107]; int n, m, u, v; int res;
int main() { while(scanf("%d %d", &n, &m) != EOF) { memset(G, 0, sizeof(G)); while(m--) { cin >> u >> v; G[u][v] = 1; } for(int k = 1; k <= n; k++) for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(G[i][k] && G[k][j]) G[i][j] = 1; res = 0; for(int i = 1; i <= n; i++) { int j; for(j = 1; j <= n; j++) { if(i == j) continue; if(!G[i][j] && !G[j][i]) break; } //cout << tmp << endl; if(j > n) res++; } cout << res << endl; } return 0; }
POJ - 3615题解：
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <string> #include <map> #include <queue> #include <algorithm> #include <iostream> using namespace std; typedef long long ll; const int Inf = 1 << 30;
int G[330][330]; int n, m, q; int u, v, w; int x, y;
int main() { scanf("%d %d %d", &n, &m, &q); for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { if(i != j) G[i][j] = Inf; else G[i][j] = 0; } } while(m--) { scanf("%d %d %d", &u, &v, &w); G[u][v] = w; } for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { for(int k = 1; k <= n; k++) { if(G[j][i] < Inf && G[i][k] < Inf) { int tmp = max(G[j][i], G[i][k]); G[j][k] = min(tmp, G[j][k]); } } } } while(q--) { scanf("%d %d", &x, &y); if(G[x][y] == Inf) puts("-1"); else printf("%d\n", G[x][y]); } }
2. 迪杰斯特拉：
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <cstdlib> #include <ctime> using namespace std; typedef long long LL;
int tu[50][50]; int dis[50], vis[50]; int n, m;
void dij() { int j, i, u, MAX; for(i = 2; i <= n; i++) { dis[i] = tu[1][i]; vis[i] = 0; } vis[1] = 1; for(i = 2; i <= n; i++) { MAX = 1 << 20; for(j = 1; j <= n; j++) { if(vis[j] == 0 && dis[j] < MAX) { MAX = dis[j]; u = j; } } vis[u] = 1; for(j = 1; j <= n; j++) { if(vis[j] == 0 && dis[j] > tu[u][j] + dis[u]) dis[j] = tu[u][j] + dis[u]; } } }
int main() { int i, j, x, y, c; cin >> n >> m; for(i = 1; i <= n; i++) for(j = 1; j <= m; j++) tu[i][j] = 1 << 20; for(i = 1; i <= m; i++) { cin >> x >> y >> c; tu[x][y] = c; tu[y][x] = c; } dij(); cout<< dis[n] << endl; return 0; }
对应题目：POJ3268
题解：
#include <cstdio> #include <cstdlib> #include <cstring> #include <vector> #include <queue> #include <set> #include <map> #include <cmath> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; const int Inf = 1 << 30; const int maxx = 1e3 + 7;
int G[maxx][maxx]; int dis[maxx], diss[maxx]; bool vis[maxx]; int n, m, p; int u, v, w;
int Dij() { int minT; int u; memset(vis, 0, sizeof(vis)); for(int i = 1; i <= n; i++) { dis[i] = G[p][i]; diss[i] = G[i][p]; } for(int i = 1; i <= n; i++) { minT = Inf; for(int j = 1; j <= n; j++) { if(!vis[j] && dis[j] < minT) { minT = dis[j]; u = j; } } vis[u] = 1; for(int j = 1; j <= n; j++) { if(!vis[j] && dis[j] > G[u][j] + dis[u]) dis[j] = G[u][j] + dis[u]; } } memset(vis, 0, sizeof(vis)); for(int i = 1; i <= n; i++) { minT = Inf; for(int j = 1; j <= n; j++) { if(!vis[j] && diss[j] < minT) { minT = diss[j]; u = j; } } vis[u] = 1; for(int j = 1; j <= n; j++) { if(!vis[j] && diss[j] > G[j][u] + diss[u]) diss[j] = G[j][u] + diss[u]; } } int maxT = -Inf; for(int i = 1; i <= n; i++) maxT = max(maxT, dis[i] + diss[i]); return maxT; }
int main() { while(scanf("%d %d %d", &n, &m, &p) != EOF) { for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { if(i != j) G[i][j] = Inf; else G[i][j] = 0; } } while(m--) { cin >> u >> v >> w; G[u][v] = w; } cout << Dij() << endl; } return 0; }
3. SPFA：
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <queue> #include <algorithm> using namespace std; typedef long long LL; const int MaxN = 1e5; const LL INF = 1e9; bool vis[MaxN + 5]; int all; int n, m; int pre[2 * MaxN + 5], last[MaxN + 5], other[2 * MaxN + 5], cost[2 * MaxN + 5]; LL dis[MaxN + 5];
void Build(int u, int v, int w) { pre[++all] = last[u]; last[u] = all; other[all] = v; cost[all] = w; }
void Spfa(int x) { queue<int>que; for(int i = 1; i <= n; i++) dis[i] = INF, vis[i] = 0; vis[x] = 1, dis[x] = 0; que.push(x); while(!que.empty()) { int pos = que.front(); que.pop(); int ed = last[pos]; while(ed != -1) { int dr = other[ed]; int w = cost[ed]; if(dis[dr] > dis[pos] + w) { dis[dr] = dis[pos] + w; if(!vis[dr]) { vis[dr] = 1; que.push(dr); } } ed = pre[ed]; } vis[pos] = 0; } }
int main() { while(~scanf("%d %d", &n, &m)) { if(n == 0 && m == 0) break; memset(last, -1, sizeof(last)); all = -1; for(int i = 1; i <= m; i++) { int x, y, w; scanf("%d %d %d", &x, &y, &w); Build(x, y, w); Build(y, x, w); } Spfa(1); printf("%d\n", dis[n]); } return 0; }
