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; }