1125.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1125 on 2006-01-19 at 04:38:03 */ 
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

const int L_MAX = 32;
const int MAX = 128;
const int INFINITE = 10000;

class Road {
public:
	int begin, end;
	bool pass;
	Road(int, int);
};
Road::Road(int b = 0, int e = 0) {
	begin = b; end = e;
}

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

map<const char*, int, cmp> dict;
vector<Road> road[MAX][MAX];
Road path;
char num[8];
int cn;

char* parse(int);
void Dijkstra(int, int, int);

int main()
{
	int n, m, early, t = 0;
	int i, j, src, dis;
	char city[MAX][L_MAX];
	char name[L_MAX];

	while(scanf("%d", &cn) != EOF && cn != 0) {
		dict.clear();
		for(i = 0; i < cn; i++) {
			scanf("%s", city[i]);
			dict[city[i]] = i;
		}
		for(i = 0; i < cn; i++)
			for(j = 0; j < cn; j++) 
				road[i][j].clear();
		scanf("%d", &n);
		for(i = 0; i < n; i++) {
			scanf("%d", &m);
			int prev, prevt;
			for(j = 0; j < m; j++) {
				int now, time;
				scanf("%d %s", &time, name);
				now = dict.find(name)->second;
				if(j != 0) road[prev][now].push_back(Road(prevt, time));
				prev = now;
				prevt = time;
			}
		}
		scanf("%d", &early);
		scanf("%s", name);
		src = dict.find(name)->second;
		scanf("%s", name);
		dis = dict.find(name)->second;
		path.pass = false;
		printf("Scenario #%d\n", ++t);
		Dijkstra(src, dis, early);
		if(!path.pass) printf("No connection\n");
		else {
			printf("Departure %s %s\n", parse(path.begin), city[src]);
			printf("Arrival   %s %s\n", parse(path.end), city[dis]);
		}
		putchar('\n');
	}
	
	return 0;
}

char* parse(int a)
{
	int i;
	num[4] = 0;
	for(i = 3; i >= 0; i--, a /= 10) num[i] = a%10+'0';
	return num;
}
void Dijkstra(int src, int dis, int early)
{
	bool visit[MAX] = {false};
	int time[MAX], up[MAX] = {0};
	int i, j, mint, mini;
	for(i = 0; i < cn; i++) time[i] = INFINITE;
	visit[src] = true;
	for(i = 0; i < cn; i++)
		if(i != src && !road[src][i].empty()) {
			vector<Road>::iterator it;
			for(it = road[src][i].begin(); it != road[src][i].end(); it++)
				if((*it).begin >= early)
					time[i] = min(time[i], (*it).end);
		}
	for(i = 0; i < cn; i++) {
		mint = INFINITE;
		for(j = 0; j < cn; j++)
			if(!visit[j] && mint > time[j])
				mint = time[j], mini = j;
		if(mint == INFINITE) return;
		else if(mini == dis) {
			path.end = time[dis];
			break;
		} else {
			visit[mini] = true;
			for(j = 0; j < cn; j++)
				if(!visit[j] && !road[mini][j].empty()) {
					vector<Road>::iterator it;
					for(it = road[mini][j].begin(); it != road[mini][j].end(); it++)
						if((*it).begin >= time[mini]) 
							time[j] = min(time[j], (*it).end);
				}
		}
	}
	memset(visit, false, sizeof(visit));
	visit[dis] = true;
	for(i = 0; i < cn; i++)
		if(i != dis && !road[i][dis].empty()) {
			vector<Road>::iterator it;
			for(it = road[i][dis].begin(); it != road[i][dis].end(); it++)
				if((*it).end == time[dis]) 
					up[i] = max(up[i], (*it).begin);
		}
	for(i = 0; i < cn; i++) {
		mint = -1;
		for(j = 0; j < cn; j++)
			if(!visit[j] && mint < up[j])
				mint = up[j], mini = j;
		if(mint == -1) return;
		else if(mini == src) {
			path.pass = true;
			path.begin = up[src];
			break;
		} else {
			visit[mini] = true;
			for(j = 0; j < cn; j++)
				if(!visit[j] && !road[j][mini].empty()) {
					vector<Road>::iterator it;
					for(it = road[j][mini].begin(); it != road[j][mini].end(); it++)
						if((*it).end <= up[mini]) 
							up[j] = max(up[j], (*it).begin);
				}
		}
	}
}