時間限制: 1 s 空間限制: 128000 KB 題目等級 : 黃金 Gold 題目描述 Description
已知n個點(n<=100),給你n*n的方陣,a[i,j]表示從第i個點到第j個點的直接距離。
現在有Q個詢問,每個詢問兩個正整數,a和b,讓你求a到b之間的最短路程。
滿足a[i,j]=a[j,i];
輸入描述 Input Description第一行一個正整數n,接下來n行每行n個正整數,滿足a[i,i]=0,再一行一個Q,接下來Q行,每行兩個正整數a和b。
輸出描述 Output Description一共Q行,每行一個整數。
樣例輸入 Sample Input3
0 1 1
1 0 3
1 3 0
1
2 3
樣例輸出 Sample Output2
數據范圍及提示 Data Size & Hintn<=100,Q可能非常大。g[i][j]均>=0
請使用flyod算法
使用C/C++的同學請注意:由於輸入數據較大,使用cin和cout會導致程序超時。請使用scanf與printf進行輸入和輸出。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 int map[1001][1001]; 6 int main() 7 { 8 memset(map,0x7f,sizeof(map)); 9 int n; 10 scanf("%d",&n); 11 for(int i=1;i<=n;i++) 12 { 13 for(int j=1;j<=n;j++) 14 { 15 int w; 16 scanf("%d",&w); 17 map[i][j]=w; 18 map[j][i]=w; 19 } 20 } 21 for(int k=1;k<=n;k++) 22 { 23 for(int i=1;i<=n;i++) 24 { 25 for(int j=1;j<=n;j++) 26 { 27 if(map[i][j]>map[i][k]+map[k][j]) 28 { 29 map[i][j]=map[i][k]+map[k][j]; 30 } 31 } 32 } 33 } 34 int m; 35 scanf("%d",&m); 36 for(int i=1;i<=m;i++) 37 { 38 int a,b; 39 scanf("%d%d",&a,&b); 40 printf("%d\n",map[a][b]); 41 } 42 return 0; 43 }