AOJ_2283 Seishun 18 Kippu
問題
解法
駅は番号で管理するとやりやすい。駅名と駅番号を対応付けるためにmapをつかう。
あとはダイクストラかワーシャルフロイドすればいい。
#include <iostream> #include <cstdio> #include <vector> #include <string> #include <map> #include <queue> #include <algorithm> using namespace std; const int INF = 1 << 29; const int MAX_N = 502; int T[MAX_N][MAX_N]; int N, M; int dijk(int a, int b){ typedef pair<int, int> P; int d[N]; priority_queue<P, vector<P>, greater<P> > Q; fill(d, d + N, INF); Q.push(P(0, a)); while(!Q.empty()){ int dist = Q.top().first; int pos = Q.top().second; Q.pop(); if(d[pos] <= dist) continue; d[pos] = dist; for(int i = 0; i < N; i++){ if(d[i] > dist + T[pos][i]) Q.push(P(dist + T[pos][i], i)); } } return d[b]; } int main(){ while(cin >> N >> M && N){ typedef map<string, int> TABLE; TABLE table; int tn = 3; string S, P, G; table.clear(); for(int i = 0; i <= N; i++) for(int j = 0; j <= N; j++) T[i][j] = INF; cin >> S >> P >> G; table.insert(TABLE::value_type(S, 0)); table.insert(TABLE::value_type(P, 1)); table.insert(TABLE::value_type(G, 2)); for(int i = 0; i < M; i++){ string a, b; int dist, lazy; cin >> a >> b; cin >> dist >> lazy; if(table.find(a) == table.end()){ table.insert(TABLE::value_type(a, tn)); tn++; } if(table.find(b) == table.end()){ table.insert(TABLE::value_type(b, tn)); tn++; } T[table[a]][table[b]] = dist / 40 + lazy; T[table[b]][table[a]] = dist / 40 + lazy; } printf("%d\n", dijk(0,1) + dijk(1, 2)); } return 0; }