#UVa:567-Risk

灆洢 2016-04-29 16:28:50

利用Floyd-Warshall演算法找出每個節點到每個節點之間的最短路徑即可。

C++(0.040)

/*******************************************************/
/* UVa 567 Risk                                        */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2016/04/29                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

int main(){
  const int INFINITY = 30;

  int X;
  int caseNumber = 0;
  while( scanf("%d", &X) != EOF ){
    vector< vector<int> > map(21, vector<int>(21, INFINITY));
    for( int i = 1 ; i <= 19 ; ++i ){
      int J;
      for( int j = 0 ; j < X ; ++j ){
        scanf("%d", &J);
        map[i][J] = map[J][i] = 1;
      }

      if( i < 19 ){
        scanf("%d", &X);
      }
    }

    for( int k = 1 ; k <= 20 ; ++k ){
      for( int i = 1 ; i <= 20 ; ++i ){
        for( int j = 1 ; j <= 20 ; ++j ){
          if( map[i][k] + map[k][j] < map[i][j] ){
            map[i][j] = map[i][k] + map[k][j];
          }
        }
      }
    }

    printf("Test Set #%d\n", ++caseNumber);

    int N;
    scanf("%d", &N);
    for( int i = 0 ; i < N ; ++i ){
      int A, B;
      scanf("%d%d", &A, &B);
      printf("%2d to %2d: %d\n", A, B, map[A][B]);
    }
    printf("\n");

  }
  return 0;
}

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料