记录编号	27363	评测结果	AAAAAAAAAAA
题目名称	[USACO Nov09] 找工作	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2011-09-18 18:41:03	内存使用	0.88 MiB

#include <cstdio>
const int INF = 0x7FFFFFF;
int D, P, C, F, S;
int g[221][221], d[221], q[100001], t[221];
bool e[221][221], f[221];
int t1, t2, t3, i, j, k, ans;
void SPFA(int start) {
	for(int i=0; i<=C; i++)
		d[i] = INF;
	q[1] = start;
	f[start] = true;
	d[start] = -D;
	t[start] = 1;
	int head = 0, tail = 1;
	while(head<tail) {
        head++;
        for(int i=1; i<=C; i++)
            if(e[q[head]][i] && d[q[head]] + g[q[head]][i] < d[i]) {
                d[i] = d[q[head]] + g[q[head]][i];
                if(!f[i]) {
                    q[++tail] = i;
                    f[i] = true;
                    t[i]++;
                    if(t[i] > C) {
                        ans = 1;
                        return;
                    }
                }
            }
        f[q[head]] = false;
    }
   for(int i=1; i<=C; i++)
		if(d[i] < ans)
			ans = d[i];
}
int main() {
	freopen("jobhunt.in","r",stdin);
	freopen("jobhunt.out","w",stdout);
	scanf("%d %d %d %d %d\n", &D, &P, &C, &F, &S);
	for(int i=1; i<=P; i++) {
		scanf("%d %d\n", &t1, &t2);
		g[t1][t2] = -D;
		e[t1][t2] = true;
	}
	for(int i=1; i<=F; i++) {
		scanf("%d %d %d\n", &t1, &t2, &t3);
		if(!e[t1][t2]) {
			g[t1][t2] = -D + t3;
			e[t1][t2] = true;
		}
	}
	SPFA(S);
	printf("%d\n", -ans);
	return 0;
}