#include<bits/stdc++.h> using namespace std; int map1[1001][1001]; int dis[1001]; bool vis[1001]; int n, m; int MAX = 0xfffff; void fun(int start, int end) { memset(vis, false, sizeof(vis)); for (int i = 1; i <= n; i++) { dis[i] = map1[start][i]; } for (int i = 1; i <= n; i++) { int temp = MAX; int k = 0; for (int j = 1; j <= n; j++) { if (!vis[j]&&dis[j]<temp) { temp = dis[j]; k = j; } } vis[k] = true; for (int j = 1; j <= n; j++) { if (!vis[j] && dis[j] > dis[k] + map1[k][j]) { dis[j] = dis[k] + map1[k][j]; } } } cout << dis[end] << endl; } int main() { int k; while (cin>>n>>m>>k) { if (n==0) { break; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { map1[i][j] = MAX; } } for (int i = 1; i <= m; i++) { int x, y, d; cin >> x >> y >> d; map1[x][y] = d; map1[y][x] = d; } int start, end; for (int i = 0; i < k; i++) { cin >> start >> end; fun(start, end); } } } |
Double click to view unformatted code.