[ITSA Exam.58] Problem 4. 購物商圈(C++)

解釋
M = 5

測資s=3，e=4
代表從商店3到商店四的最短距離。
回到上面整理的資料，看十字的圖形。

       2+1=3                             5+1=6                             2+3=5                  1+0=1                   1+0=1
所以最小值為1
在看表格

由此可知，當s=3，e=4時，只要把第三列跟第四列的值，一一相加，找最小值即可。
---------------------------------------------------------------------------------------
所以，當s=0，e=2時

       0+9=9                           5+8=13                    9+0=9                          2+5=7                     1+1=2
所以最小值為2
---------------------------------------------------------------------------------------
不然再試一組測資，s=1,e=0

        0+5=5                          5+0=5                     9+8=17                       2+3=5                      1+2=3
所以最小值為3

1. #include <iostream>  
2. using namespace std;  
3.   
4. int main() {  
5.     // pro3  
6.     int n,m, min=0, p, q;  
7.     bool fir = true;  
8.     cin >> n >> m;  
9.     int PQ[m][m];  
10.     for(int i=0;i<m;i++)  
11.     {  
12.         for(int j=0;j<m;j++)  
13.         {  
14.             cin >> PQ[i][j];  
15.         }  
16.     }  
17.     for(int j = 0;j<n;j++)  
18.     {  
19.         cin >> p >> q;  
20.         for(int i = 0;i<m;i++)  
21.         {  
22.             if(fir)  
23.             {  
24.                 min = PQ[p][i]+PQ[q][i];  
25.                 fir = false;  
26.             }  
27.             else if(PQ[p][i]+PQ[q][i] < min)  
28.             {  
29.                 min = PQ[p][i]+PQ[q][i];  
30.             }  
31.         }  
32.   
33.         cout << min << endl;  
34.         min=0;  
35.         fir = true;  
36.     }  
37.     return 0;  
38. }