uva 423 - MPI Maelstrom

 1 /*
 2  Problem link
 3  Type: Graph
 4  Algorithm:
 5      Use Floyd or Dijkstra to find the shortest path from 1 to n-1 others nodes.
 6      Find the max of the shortest path from 1 to n-1 others nodes.
 7  */
 8  #include <iostream>
 9  #include <cstdio>
10  #include <cstring>
11  #include <cmath>
12  using namespace std;
13  
14  const int maxn = 110;
15  const int oo = 2000000;
16  
17  int solve();
18  
19  int a[maxn][maxn];
20  int n;
21  
22  int main()
23  {
24      cin >> n;
25      for (int i=0; i<=n; i++)
26          for (int j=0; j<=n; j++) a[i][j] = oo;
27      for (int i=1; i<=n; i++) a[i][i] = 0;
28      string value;
29      for (int i=2; i<=n; i++)
30          for (int j=1; j<=i-1; j++)
31          {
32              cin >> value;
33              if (value!="x")
34              {
35                  int tmp = 0;
36                  for (int k=0; k<value.length(); k++)
37                      tmp = tmp*10 + int(value[k])-48;
38                  a[i][j] = tmp;
39                  a[j][i] = a[i][j];
40              }
41          }
42      cout << solve() << endl;
43      return 0;
44  }
45  
46  int solve() {
47      int result = 0;
48      for (int k=1; k<=n; k++)
49          for (int i=1; i<=n; i++)
50              for (int j=1; j<=n; j++)
51                  if (a[i][j]>a[i][k]+a[k][j]) a[i][j] = a[i][k]+a[k][j];
52      for (int i=1; i<=n; i++) result = max(result,a[1][i]);
53      return(result);
54  }