1948.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1948 on 2006-03-07 at 20:23:00 */ 
#include <cstdio>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std;

const int MAX = 128;
const int L = 32;
const int INF = 1 << 30;
const int CHG_COST[][2] = { { 3, 10 }, { 10, 3 } };
const char SRC[] = "Harbin";

struct cmp {
	bool operator ()(const char* s1, const char* s2) const {
		return strcmp(s1, s2) < 0;
	}
};

map<const char*, int, cmp> city;
int n, net[2][MAX][MAX];
char name[MAX][L];

int find(const char*);
int dijkstra(int, int);

int main()
{
	char ca[L], cb[L], way[L], dis[L];
	int d, i;

	while(gets(dis) != NULL) {
		int rn; scanf("%d", &rn);
		city.clear(); n = 0; memset(net, -1, sizeof(net));
		for(i = 0; i < rn; i++) {
			scanf("%s %s %s %d\n", way, ca, cb, &d);
			int on = !strcmp(way, "train") ? 0 : 1;
			int oa = find(ca), ob = find(cb);
			net[on][oa][ob] = net[on][ob][oa] = d;
		}
		printf("%d\n", dijkstra(city.find(SRC)->second, city.find(dis)->second));
	}
	
	return 0;
}

int find(const char* cn)
{
	if(city.count(cn) == 0) {
		strcpy(name[n], cn);
		city[name[n]] = n; n++;
	}
	return city.find(cn)->second;
}

int dijkstra(int src, int dis)
{
	int d[2*MAX], i;
	bool vst[2*MAX] = { false };
	for(i = 0; i < 2*n; i++) d[i] = INF;
	d[2*src] = d[2*src+1] = 0;
	while(true) {
		int mind = INF, mini;
		for(i = 0; i < 2*n; i++)
			if(!vst[i] && mind > d[i])
				{ mind = d[i]; mini = i; }
		int cn = mini >> 1, co = mini & 1;
		if(cn == dis) return mind;
		vst[mini] = true;
		for(i = 0; i < 2*n; i++)
			if(!vst[i] && net[i&1][cn][i>>1] != -1) {
				int cost = d[mini] + net[i&1][cn][i>>1];
				if(cn != src) cost += CHG_COST[co][i&1];
				d[i] = min(d[i], cost);
			}
	}
}