#include <bits/stdc++.h> using namespace std; #define MAX 999999 int main() { int n, m, k; int s[100][100]; // 邻接矩阵 int a, b, c; while (cin >> n >> m >> k) { //n个点,m个边 for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) //邻接矩阵对角线 if (i == j) s[i][j] = 0; else s[i][j] = MAX; for (int i = 0; i < m; i++) { // 距离 scanf("%d %d %d", &a, &b, &c); s[a][b] = c; s[b][a] = c; } for (int k = 0; k < n; k++) //Floyd for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (s[i][j] > s[i][k] + s[k][j]) s[i][j] = s[i][k] + s[k][j]; for (int i = 0; i < k; i++) { scanf("%d %d", &a, &b); printf("%d\n", s[a][b]); } } } |
Double click to view unformatted code.