2147.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2147 on 2006-03-02 at 12:29:17 */ 
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX = 1120;
const int INF = 1 << 30;

class Road {
public:
	int town, cost, dis;
	Road(int t, int c, int d) : town(t), cost(c), dis(d) {}
};

class Town {
public:
	vector<Road> adj;
	int minc;
	void clear();
	void insert(int, int, int);
};
void Town::clear() {
	adj.clear(); minc = INF;
}
void Town::insert(int t, int c, int d) {
	if(minc < c) return;
	else if(minc > c) { minc = c; adj.clear(); }
	adj.push_back(Road(t, c, d));
}

class City {
private:
	Town town[MAX];
	int n;
public:
	int pay[MAX], dst[MAX], vn;
	bool vst[MAX];
	void make(int, int);
	bool connect(int, int);
	void travel(int, int);
};
void City::make(int cn, int m) {
	int i; n = cn;
	for(i = 0; i < n; i++) town[i].clear();
	for(i = 0; i < m; i++) {
		int a, b, pc, nc, d;
		scanf("\n(%d,%d,%d[%d]%d)", &a, &b, &pc, &d, &nc);
		town[a].insert(b, pc, d); town[b].insert(a, nc, d);
	}
}
bool City::connect(int src, int dis) {
	memset(vst, false, sizeof(vst));
	int i, j, stack[MAX], top = 0;
	stack[top++] = dis; vst[dis] = true; vn = 1;
	vector<int> next[MAX];
	for(i = 0; i < n; i++)
		for(j = 0; j < (int)town[i].adj.size(); j++)
			next[town[i].adj[j].town].push_back(i);
	while(top > 0) {
		int p = stack[--top];
		for(i = 0; i < (int)next[p].size(); i++) {
			int o = next[p][i];
			if(!vst[o]) { vn++; vst[o] = true; stack[top++] = o; }
		}
	}
	return vst[src];
}
void City::travel(int src, int dis) {
	bool change[MAX] = { false }, temp[MAX];
	int i, j, k; bool ex = true;
	for(i = 0; i < n; i++) pay[i] = dst[i] = INF;
	pay[src] = dst[src] = 0; change[src] = true;
	for(i = 0; i <= vn && ex; i++) {
		ex = false; memset(temp, false, sizeof(temp));
		for(j = 0; j < n; j++) {
			if(!change[j] || !vst[j]) continue;
			for(k = 0; k < (int)town[j].adj.size(); k++) {
				Road &r = town[j].adj[k];
				if(pay[r.town] > pay[j]+r.cost || 
					(pay[r.town] == pay[j]+r.cost && dst[r.town] > dst[j]+r.dis)) {
					ex = temp[r.town] = true;
					pay[r.town] = pay[j] + r.cost; dst[r.town] = dst[j] + r.dis;
				}
			}
		}
		memcpy(change, temp, sizeof(temp));
		if(i == vn && ex) { pay[dis] = -INF; break; }
	}
}

int main()
{
	City city;
	int n, m, s, t;

	while(scanf("%d %d %d %d", &n, &m, &s, &t) != EOF) {
		city.make(n, m);
		if(!city.connect(s, t)) printf("VOID\n");
		else {
			city.travel(s, t);
			if(city.pay[t] == -INF) printf("UNBOUND\n");
			else printf("%d %d\n", city.pay[t], city.dst[t]);
		}
	}
	
	return 0;
}