单源最短路径dijkstra，水题 本题要点： 1、n <= 200, 直接用邻接矩阵存图，重边的话取最小值。套用 dijkstra 模板。
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int MaxN = 210; int n, m, s, t; int a[MaxN][MaxN], d[MaxN]; bool vis[MaxN]; void dijkstra() { memset(d, 0x3f, sizeof d); memset(vis, false, sizeof vis); d[s] = 0; for(int i = 1; i < n; ++i) // 重复 n - 1 次 { int x = -1; for(int j = 0; j < n; ++j) { if(!vis[j] && (-1 == x || d[j] < d[x])) x = j; } if(-1 == x) return; vis[x] = 1; // 利用 全局最小值点x更新其他值 for(int y = 0; y < n; ++y) { d[y] = min(d[y], d[x] + a[x][y]); } } } int main() { int x, y, z; while(scanf("%d%d", &n, &m) != EOF) { memset(a, 0x3f, sizeof a); for(int i = 0; i < n; ++i) { a[i][i] = 0; } for(int i = 0; i < m; ++i) { scanf("%d%d%d", &x, &y, &z); a[x][y] = min(a[x][y], z); a[y][x] = min(a[y][x], z); } scanf("%d%d", &s, &t); dijkstra(); if(d[t] == 0x3f3f3f3f) { printf("-1\n"); }else{ printf("%d\n", d[t]); } } return 0; } /* 3 3 0 1 1 0 2 3 1 2 1 0 2 3 1 0 1 1 1 2 */ /* 2 -1 */