UVa 186 Trip Routing

Trip Routing
http://uva.onlinejudge.org/external/1/186.html

問題概要

場所の名前と場所同士をつなぐ道路の長さと名前が与えられる。
異なる2点の最短経路を求めるクエリがくるから、パスと最短距離を答えよ。

解法

ワーシャルフロイド

パスの復元、ワーシャルフロイドで初めてした気がする。
入力をとるのが結構めんどくさい。

ソース

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<cstdlib>
#include<cstdio>
#include<cstring>

#define REP(i,b,n) for(int i=b;i<(int)n;i++)
#define rep(i,n)   REP(i,0,n)
#define FOR(it,o)  for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it)

using namespace std;
const double EPS = 0.00000001;
const int INF = 1000000000;
typedef long long lli;

const int N = 100;

string cityName[N], edgeName[N][N];
int inCost[N][N], cost[N][N], pre[N][N];
const string intro = "\n\nFrom                 To                   Route      Miles\n"
"-------------------- -------------------- ---------- -----\n";
const string tail = "                                                     -----\n"
"                                          Total      ";
map<string, int> ID;
int id;

void init(){
 id = 0;
 ID.clear();
 rep(i, N){
   rep(j, N){
     cost[i][j] = INF;
     inCost[i][j] = INF;
     pre[i][j] = -1;
   }
 }
}

int getID(string s){
 if(ID.find(s) != ID.end())return ID[s];
 ID[s] = id;
 cityName[id] = s;
 id++;
 return id-1;
}

void inputEdge(){
 string s;
 while(getline(cin, s)){
   if(s.length() == 0)break;
   vector<int> pos;
   rep(i, s.length()){
     if(s[i] == ',')pos.push_back(i);
   }
   int from = getID(s.substr(0, pos[0]));
   int to = getID(s.substr(pos[0]+1, pos[1] - pos[0] - 1));
   string name =  s.substr(pos[1]+1, pos[2] - pos[1]-1);
   int nowCost = atoi(s.c_str() + pos[2] + 1);
   if(inCost[from][to] > nowCost){
     inCost[from][to] = inCost[to][from] = nowCost;
     cost[from][to] = cost[to][from] = nowCost;
     edgeName[from][to] = edgeName[to][from] = name;
   }
 }
}

void floyd(){
  rep(k, id){
   rep(i, id){
     rep(j, id){
       if(max(cost[i][k], cost[k][j]) == INF)continue;
       int tmpCost = cost[i][k] + cost[k][j];
       if(cost[i][j] > tmpCost){
         cost[i][j] = tmpCost;
         pre[i][j] = k;
       }
     }
   }
 }
}

pair<int, int> query(string s){
 int pos = 0;
 rep(i, s.length()){
   if(s[i] == ',')pos = i;
 }
 return make_pair(ID[s.substr(0, pos)], ID[s.substr(pos+1,s.length() - pos+1)]);
}

void makePath(int from, int to, vector<pair<int, int> > &P){
  if(inCost[from][to] == cost[from][to]){
    P.push_back(make_pair(from, to));
    return;
  }
  makePath(from, pre[from][to], P);
  makePath(pre[from][to], to, P);
}

void output(pair<int, int> p){
  printf("%s%s%s%5d\n", cityName[p.first].c_str(), cityName[p.second].c_str(),
         edgeName[p.first][p.second].c_str(), inCost[p.first][p.second]);
}

int main(){
 init();
 inputEdge();
 floyd();
 string s;
 while(getline(cin, s)){
   if(s.length() == 0)break;
   pair<int, int> Q = query(s);
   int from = Q.first, to = Q.second;
   vector<pair<int, int> > path;
   makePath(from, to, path);
   rep(i, id){
     while(cityName[i].length() < 21){
       cityName[i] += ' ';
     }
   }
   rep(i, id){
     rep(j, id){
       if(inCost[i][j] != INF){
         while(edgeName[i][j].length() < 11){
           edgeName[i][j] += ' ';
         }
       }
     }
   }
   printf("%s",intro.c_str());
   FOR(it, path){
     output(*it);
   }
   printf("%s%5d\n",tail.c_str(), cost[Q.first][Q.second]);
 }
 return 0;
}