uva 186 - Trip Routing

  1  /*
  2  Problem link
  3  Type: Graph
  4  Algorithm: Floyd
  5  */
  6  #include <iostream>
  7  #include <cstdio>
  8  #include <sstream>
  9  #include <cstdlib>
 10  #include <cmath>
 11  #include <cstring>
 12  #include <map>
 13  #include <vector>
 14  #include <iomanip>
 15  
 16  using namespace std;
 17  const int maxn = 510;
 18  const int oo = 999999;
 19  
 20  class Route
 21  {
 22  public:
 23      int x,y;
 24      Route(int xx, int yy): x(xx), y(yy) {}
 25      bool operator>(const Route& R) const
 26      {
 27          if (x>R.x) return(true);
 28          if (x == R.x && y>R.y) return(true);
 29          return(false);
 30      }
 31      bool operator<(const Route& R) const
 32      {
 33          if (x<R.x) return(true);
 34          if (x == R.x && y<R.y) return(true);
 35          return(false);
 36      }
 37      bool operator==(const Route& R) const
 38      {
 39          if (x == R.x && y == R.y) return(true);
 40          return(false);
 41      }
 42  };
 43  
 44  int f[maxn][maxn],pre[maxn][maxn];
 45  map<Route,string> RouteName;
 46  map<string,int> City;
 47  map<int,string> CityName;
 48  map<string,string> OldName;
 49  int n;
 50  
 51  void readfile();
 52  void floyd();
 53  int solve(string c1, string c2, vector<string> &ans);
 54  
 55  int main()
 56  {
 57      readfile();
 58      floyd();
 59      vector<string> ans;
 60      string line;
 61      stringstream ss;
 62      getline(cin,line);
 63      while (line!="" && !cin.eof())
 64      {
 65          cout << endl << endl;
 66          ss.clear();
 67          for (unsigned int i=0; i<line.length(); i++)
 68              if (line[i]==',') line[i] = ' ';
 69              else if (line[i]==' ') line[i] = '+';
 70          ss << line;
 71          string c1,c2;
 72          ss >> c1 >> c2;
 73          cout << "From" << setw(21-2) << "To" << setw(21-2+5) << "Route"
 74               << setw(11) << "Miles" << setw(5) << endl;
 75          cout << "-------------------- -------------------- ---------- -----" << endl;
 76          int result = solve(c1,c2,ans);
 77          for (unsigned int i=0; i<ans.size()-1; i++)
 78          {
 79              string rN = RouteName[Route(City[ans[i]],City[ans[i+1]])];
 80              c1 = ans[i]; c2 = ans[i+1];
 81              for (unsigned int j=0; j<c1.length(); j++)
 82                  if (c1[j]=='+') c1[j] = ' ';
 83              for (unsigned int j=0; j<c2.length(); j++)
 84                  if (c2[j]=='+') c2[j] = ' ';
 85              int nL = 0, x = f[City[ans[i]]][City[ans[i+1]]];
 86              while (x>0) { x/=10; nL++; }
 87              cout << c1 << setw(21-ans[i].length()+ans[i+1].length()) << c2 << setw(21-ans[i+1].length()+rN.length())
 88                   << rN << setw(11-rN.length()+5) << f[City[ans[i]]][City[ans[i+1]]] << endl;
 89          }
 90          cout << setw(58) << "-----" << endl;
 91          cout << setw(47) << "Total" << setw(11) << result << endl;
 92          getline(cin,line);
 93      }
 94      return 0;
 95  }
 96  
 97  void readfile()
 98  {
 99      stringstream ss;
100      string line;
101      n = 0;
102      getline(cin,line);
103      for (int i=0; i<maxn; i++)
104          for (int j=0; j<maxn; j++) f[i][j] = +oo;
105      while (line!="" && !cin.eof())
106      {
107          for (unsigned int i=0; i<line.length(); i++)
108              if (line[i]==',') line[i] = ' ';
109              else if (line[i]==' ') line[i] = '+';
110          ss << line;
111          string c1,c2,rName;
112          int rLength;
113          ss >> c1 >> c2 >> rName >> rLength;
114          map<string,int>::iterator iter;
115          iter = City.find(c1);
116          if (iter == City.end())
117          {
118              City[c1] = ++n;
119              CityName[n] = c1;
120          }
121          iter = City.find(c2);
122          if (iter == City.end())
123          {
124              City[c2] = ++n;
125              CityName[n] = c2;
126          }
127          map<Route,string>::iterator iter2;
128          iter2 = RouteName.find(Route(City[c1],City[c2]));
129          if (iter2 == RouteName.end())
130          {
131              RouteName[Route(City[c1],City[c2])] = rName;
132              RouteName[Route(City[c2],City[c1])] = rName;
133              f[City[c1]][City[c2]] = rLength;
134              f[City[c2]][City[c1]] = rLength;
135          }
136          else if (rLength<f[City[c1]][City[c2]])
137          {
138              RouteName[Route(City[c1],City[c2])] = rName;
139              RouteName[Route(City[c2],City[c1])] = rName;
140              f[City[c1]][City[c2]] = rLength;
141              f[City[c2]][City[c1]] = rLength;
142          }
143          line = "";
144          getline(cin,line);
145          ss.clear();
146      }
147  }
148  
149  void floyd()
150  {
151      for (int i=1; i<=n; i++)
152          for (int j=1; j<=n; j++) pre[i][j] = j;
153      for (int i=1; i<=n; i++) f[i][i] = 0;
154  
155      for (int k=1; k<=n; k++)
156          for (int i=1; i<=n; i++)
157              for (int j=1; j<=n; j++)
158                  if (f[i][j]>f[i][k]+f[k][j])
159                  {
160                      f[i][j] = f[i][k] + f[k][j];
161                      pre[i][j] = pre[i][k];
162                  }
163  }
164  
165  int solve(string c1, string c2, vector<string> &ans)
166  {
167      ans.clear();
168      int i = City[c1],
169          j = City[c2],
170          x = i;
171      while (x!=j)
172      {
173          ans.push_back(CityName[x]);
174          x = pre[x][j];
175      }
176      ans.push_back(CityName[j]);
177      return(f[i][j]);
178  }