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