uva 10171 - Meeting Prof. Miguel...

  1  /*
  2  Problem link
  3  Type: Graph - Floyd
  4  Algorithm:
  5      I use 2 graphs (adjacent matrix) aM and aY to store the path of 2 persons
  6      Run floyd seperately on each graph
  7      Find a City that reachable from both persons and minimize the costs
  8  
  9      Note:
 10      There may be many roads with the same ends but different energy and person
 11      -> choose the best one for each person
 12  
 13      For graph which has the name of each nodes, I usually use two maps (C++ map)
 14      to convert from name to index and index to name.
 15  */
 16  #include <iostream>
 17  #include <cstdio>
 18  #include <map>
 19  #include <cstring>
 20  #include <cmath>
 21  #include <vector>
 22  #include <algorithm>
 23  
 24  using namespace std;
 25  const char* fi = "10171.inp";
 26  const char* fo = "10171.out";
 27  const int maxn = 30;
 28  const int oo = 1000000;
 29  
 30  int aM[maxn][maxn], aY[maxn][maxn];
 31  int m, n, s, t;
 32  map<char, int> CityIndex;
 33  map<int, char> CityName;
 34  
 35  bool ReadFile();
 36  void ConnectM();
 37  void ConnectY();
 38  int Solve(vector<char>& Cities);
 39  
 40  int main()
 41  {
 42      while (ReadFile())
 43      {
 44          ConnectM();
 45          ConnectY();
 46          vector<char> Cities;
 47          Cities.clear();
 48          int result = Solve(Cities);
 49  
 50          if (result!=oo)
 51          {
 52              cout << result << " ";
 53              sort(Cities.begin(), Cities.end());
 54  
 55              for (unsigned int i = 0; i < Cities.size()-1; i++) cout << Cities[i] << " ";
 56              cout << *(Cities.rbegin()) << endl;
 57          }
 58          else cout << "You will never meet." << endl;
 59      }
 60      return 0;
 61  }
 62  
 63  bool ReadFile()
 64  {
 65      cin >> m;
 66      if (m == 0) return false;
 67  
 68      n = 0;
 69      CityIndex.clear();
 70      CityName.clear();
 71  
 72      for (int i = 0; i < maxn; i++)
 73          for (int j = 0; j < maxn; j++)
 74          {
 75              aM[i][j] = oo;
 76              aY[i][j] = oo;
 77          }
 78      for (int i = 0; i< maxn; i++)
 79      {
 80          aM[i][i] = 0;
 81          aY[i][i] = 0;
 82      }
 83  
 84      for (int i = 1; i <= m; i++)
 85      {
 86          char c1,c2,c3,c4;
 87          int value;
 88  
 89          cin >> c1 >> c2 >> c3 >> c4 >> value;
 90          if (CityIndex.count(c3) <= 0)
 91          {
 92              n++;
 93              CityIndex[c3] = n;
 94              CityName[n] = c3;
 95          }
 96          if (CityIndex.count(c4) <= 0)
 97          {
 98              n++;
 99              CityIndex[c4] = n;
100              CityName[n] = c4;
101          }
102  
103          int k = CityIndex[c3], j = CityIndex[c4];
104          if (c1 == 'M')
105          {
106              aM[k][j] = min(aM[k][j],value);
107              if (c2 == 'B') aM[j][k] = min(aM[j][k],value);
108          }
109          else
110          {
111              aY[k][j] = min(aY[k][j],value);
112              if (c2 == 'B') aY[j][k] = min(aY[j][k],value);
113          }
114      }
115  
116      char cs, ct;
117      cin >> cs >> ct;
118      s = CityIndex[cs];
119      t = CityIndex[ct];
120      return true;
121  }
122  
123  void ConnectM()
124  {
125      for (int k = 1; k <= n; k++)
126          for (int i = 1; i <= n; i++)
127              for (int j = 1; j <= n; j++)
128                  if (aM[i][j] >  aM[i][k] + aM[k][j]) aM[i][j] = aM[i][k] + aM[k][j];
129  }
130  
131  void ConnectY()
132  {
133      for (int k = 1; k <= n; k++)
134          for (int i = 1; i <= n; i++)
135              for (int j = 1; j <= n; j++)
136                  if (aY[i][j] > aY[i][k] + aY[k][j]) aY[i][j] = aY[i][k] + aY[k][j];
137  }
138  
139  int Solve(vector<char>& Cities)
140  {
141      int result = oo;
142  
143      for (int k = 1; k <= n; k++)
144          if (aY[s][k] + aM[t][k] < result) result = aY[s][k] + aM[t][k];
145  
146      for (int k = 1; k <= n; k++)
147          if (aY[s][k] + aM[t][k] == result) Cities.push_back(CityName[k]);
148  
149      return result;
150  }