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

在假設(shè)所有邊都是最大值的情況下，如果第一個(gè)人能比第二個(gè)人先到，那就縮短這條邊。

代碼：

#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"); }

　　

轉(zhuǎn)載于:https://www.cnblogs.com/pkgunboat/p/11129831.html

總結(jié)

以上是生活随笔為你收集整理的Codeforces 360E 贪心 最短路的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。