Floyd-Warshall算法
#include <iostream> using namespace std; int map[101][101]; int n, m; int inf = 999999999; int main() { int a, b, c; while (1) { cin >> n >> m; if (n == 0 && m == 0) return 0; for(int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { if (i == j) map[i][j] = 0; else map[i][j] = inf; } for (int i = 0; i < m; i++) { cin >> a >> b >> c; map[a][b] = c; map[b][a] = c; } for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { if (map[i][j] > map[i][k] + map[k][j]) map[i][j] = map[i][k] + map[k][j]; } cout << map[1][n] << endl; } }Dijkatra算法
#include <iostream> using namespace std; int map[101][101]; int n, m; int inf = 999999999; int dis[101]; int book[101]; int main() { int a, b, c; while (1) { cin >> n >> m; if (n == 0 && m == 0) return 0; for(int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { if (i == j) map[i][j] = 0; else map[i][j] = inf; } for (int i = 0; i < m; i++) { cin >> a >> b >> c; map[a][b] = c; map[b][a] = c; } for (int i = 1; i <= n; i++) { dis[i] = map[1][i]; book[i] = 0; } for (int i = 2; i <= n; i++) { int x = 0; int min = inf; for (int j = 2; j <= n; j++) if (min > dis[j] && !book[j]) { min = dis[j]; x = j; } book[x]++; for (int j = 2; j <= n; j++) { if (book[j]) continue; if (dis[j] > dis[x] + map[x][j]) dis[j] = dis[x] + map[x][j]; } } cout << dis[n] << endl; } }