此文为博主原创题解，转载时请通知博主，并把原文链接放在正文醒目位置。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <ctime> 5 using namespace std; 6 int n, map[510][510], dis[510]; 7 bool exist[510]; 8 int dij(int x, int y){ 9 dis[x] = 0; 10 for (int i = 1; i <= n; i++){ 11 int k = 0, minn = 0x5f; 12 for (int j = 1; j <= n; j++) 13 if (exist[j] == false && dis[j] < minn) 14 minn = dis[j], k = j; 15 if (k == 0) break; 16 exist[k] = true; 17 for (int j = 1; j <= n; j++) 18 if (dis[j] > dis[k] + map[k][j]) 19 dis[j] = dis[k] + map[k][j]; 20 } 21 return dis[y]; 22 } 23 int main(){ 24 scanf("%d", &n); 25 for (int i = 1; i <= n; i++) 26 for (int j = 1; j <= n; j++) 27 scanf("%d", &map[i][j]); 28 int t; 29 scanf("%d", &t); 30 while (t--){ 31 int x, y; 32 scanf("%d%d", &x, &y); 33 memset(dis, 0x3f, sizeof(dis)); 34 memset(exist, false, sizeof(exist)); 35 printf("%d ", dij(x, y)); 36 } 37 return 0; 38 }