Codeforces 360E 贪心 最短路

题意及思路：https://blog.csdn.net/huanghongxun/article/details/49846927

在假设所有边都是最大值的情况下，如果第一个人能比第二个人先到，那就缩短这条边。

代码：

#include <bits/stdc++.h>

#define LL long long

using namespace std;

const int maxn = 10010;

int head[maxn], Next[maxn * 2], ver[maxn * 2], f[maxn * 2], tot;

LL l[maxn * 2], r[maxn * 2];

LL d[2][maxn];

bool v[2][maxn];

queue<int> q[2];

int s1, s2, t, n, m, k;

void add(int x, int y, LL lb, LL rb) {

	ver[++tot] = y, l[tot] = lb, r[tot] = rb, Next[tot] = head[x], head[x] = tot, f[tot] = x;

}

void spfa(int pos, int s) {

//	memset(d[pos], 0x3f, sizeof(d[pos]));

//	memset(v[pos], 0, sizeof(v[pos]));

//	q[pos].push(s), v[pos][s] = 1, d[pos][s] = 0;

	while(q[pos].size()) {

		int x = q[pos].front();

		q[pos].pop();

		v[pos][x] = 0;

		for (int i = head[x]; i; i = Next[i]) {

			int y = ver[i], z = r[i];

			if(d[pos][y] > d[pos][x] + z) {

				d[pos][y] = d[pos][x] + z;

				if(!v[pos][y])

					q[pos].push(y), v[pos][y] = 1;

			}

		}

	}

}

bool solve(int flag) {

	memset(d, 0x3f, sizeof(d));

	memset(v, 0, sizeof(v));

	d[0][s1] = d[1][s2] =  0;

	v[0][s1] = v[1][s2] = 1;

	q[0].push(s1), q[1].push(s2);

	bool flag1 = 1;

	while(flag1) {

		spfa(0, s1), spfa(1, s2);

		flag1 = 0;

		for (int i = m + 1; i <= k + m; i++) {

			if(d[0][f[i]]  + flag <= d[1][f[i]] && l[i] != r[i]) {

				flag1 = 1;

				q[0].push(f[i]), q[1].push(f[i]);

				v[0][f[i]] = 1, v[1][f[i]] = 1;

				r[i] = l[i];

			}

		}

	}

	return d[0][t] + flag <= d[1][t];

}

int main() {

	int x, y;

	LL z, t1;

	scanf("%d%d%d", &n, &m, &k);

	scanf("%d%d%d", &s1, &s2, &t);

	for (int i = 1; i <= m; i++) {

		scanf("%d%d%lld", &x, &y, &z);

		add(x, y, z, z);

	}

	for (int i = 1; i <= k; i++) {

		scanf("%d%d%lld%lld", &x, &y, &z, &t1);

		add(x, y, z, t1);

	}

	if(solve(1)) {

		printf("WIN\n");

		for (int i = m + 1; i <= m + k; i++)

			printf("%d ", r[i]);

		printf("\n");

		return 0;

	}

	if(solve(0)) {

		printf("DRAW\n");

		for (int i = m + 1; i <= m + k; i++)

			printf("%d ", r[i]);

		printf("\n");

		return 0;

	}

	printf("LOSE\n");

}