1566.cpp

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

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

const int CN = 64, RN = 512;
const int INF = 1 << 28;

class Road {
public:
	vector<int> ct;
	int b, e, pt;
	void make();
	int pass(int) const;
};
void Road::make() {
	scanf("%d %d %d", &b, &e, &pt);
	int i; ct.clear();
	for(i = 0; true; i++) {
		char c;
		while((c = getchar()) == ' ');
		if(c == '\n') break;
		ungetc(c, stdin);
		int a; scanf("%d", &a);
		ct.push_back(a);
	}
	ct.push_back(INF<<1);
	if(ct.size()&1) ct.push_back(INF<<2);
}
int Road::pass(int t) const {
	while(true) {
		vector<int>::const_iterator bit = upper_bound(ct.begin(), ct.end(), t);
		if((bit-ct.begin())&1) t = *(bit++);
		vector<int>::const_iterator eit = lower_bound(ct.begin(), ct.end(), t+pt);
		if(bit != eit) t = *(bit+1);
		else return t+pt;
	}
}

int main()
{
	Road r[RN];
	int n, m, s, t, d[CN], i;
	
	while(scanf("%d %d %d %d", &n, &m, &s, &t) != EOF && n != 0) {
		for(i = 1; i <= n; i++) d[i] = INF; d[s] = 0;
		for(i = 0; i < m; i++) r[i].make();
		bool ex = true;
		while(ex) {
			ex = false;
			for(i = 0; i < m; i++) {
				int b = r[i].b, e = r[i].e, pb = r[i].pass(d[e]), pe = r[i].pass(d[b]);
				if(d[b] > pb) { d[b] = pb; ex = true; }
				if(d[e] > pe) { d[e] = pe; ex = true; }
			}
			if(!ex) break;
		}
		if(d[t] == INF) printf("*\n");
		else printf("%d\n", d[t]);
	}
	
	
	return 0;
}