首页 > 代码库 > CodeForces 360E Levko and Game（Codeforces Round #210 (Div. 1)）

CodeForces 360E Levko and Game（Codeforces Round #210 (Div. 1)）

2024-07-15 14:49:19   214人阅读

题意:有一些无向边m条权值是给定的k条权值在[l,r]区间可以由你来定，一个点s1 出发一个从s2出发  问s1 出发的能不能先打到f

思路：最短路。

首先检测能不能赢 在更新的时候  如果对于一条边 a->b  如果dis1[a] <dis2[a]  那么选择这条边就选择   l  因为这条边对于s1有利 如果两个起点都选择了这条边  则说明s1 赢定了，所以要让他们尽量走这条，所以边权越小越好。跑完之后检测 如果  dis1[f]<dis2[f] 那么 就赢了。

  接下来判断能不能平局。因为目前已经没有赢的可能了  那么  把dis1[a]<dis2[a]改成dis1[a]<=dis2[a] 选择l  其他选择r 即可。原因：小于的话毫无疑问就是选择l  ；等于的话选择小的如果两个都走了这条边则平局。

#include<cstring>#include<algorithm>#include<cstdio>#include<cmath>#include <iostream>#include<vector>#include<queue>#define INF 1e15#define LL long long#define P pair<LL,int>#define MP make_pair#define M 200000#define N 100000using namespace std;priority_queue<P> q;struct node {    int l, r, to, nx;} e[M];int head[N];int ecnt;int ans[N];void addedge(int x, int y, int l, int r) {    e[ecnt].l = l;    e[ecnt].r = r;    e[ecnt].to = y;    e[ecnt].nx = head[x];    head[x] = ecnt++;}LL d1[N], d2[N];int n, m, k, s1, s2, f;void gao(int bo) {    while (!q.empty())        q.pop();    memset(ans, -1, sizeof(ans));    for (int i = 0; i <= n; ++i)        d1[i] = d2[i] = INF;    d1[s1] = d2[s2] = 0;    q.push(MP(0, s1));    q.push(MP(0, s2));    while (!q.empty()) {        P ee = q.top();        q.pop();        LL va = -ee.first;        int id = ee.second;        if (va > d1[id] && va > d2[id])            continue;        bool ok;        if (bo == 1) {            if (d1[id] < d2[id])                ok = true;            else                ok = false;        } else {            if (d1[id] <= d2[id])                ok = true;            else                ok = false;        }        for (int i = head[id]; i != -1; i = e[i].nx) {            int u = e[i].to;            LL add;            if (ok)                add = e[i].l;            else                add = e[i].r;            ans[i] = add;            if (d1[u] > d1[id] + add) {                d1[u] = d1[id] + add;                q.push(MP(-d1[u], u));            }            if (d2[u] > d2[id] + add) {                d2[u] = d2[id] + add;                q.push(MP(-d2[u], u));            }        }    }}int main() {    scanf("%d%d%d", &n, &m, &k);    scanf("%d%d%d", &s1, &s2, &f);    memset(head, -1, sizeof(head));    ecnt = 0;    for (int i = 0; i < m; ++i) {        int x, y, z;        scanf("%d%d%d", &x, &y, &z);        addedge(x, y, z, z);    }    for (int i = 0; i < k; ++i) {        int x, y, l, r;        scanf("%d%d%d%d", &x, &y, &l, &r);        addedge(x, y, l, r);    }    gao(1);    if (d1[f] < d2[f]) {        puts("WIN");        for (int i = m; i < m + k; ++i) {            if (ans[i] == -1)                ans[i] = e[i].l;            printf("%d", ans[i]);            if (i == m + k - 1)                puts("");            else                printf(" ");        }        return 0;    }    gao(0);    if (d1[f] == d2[f]) {        puts("DRAW");        for (int i = m; i < m + k; ++i) {            if (ans[i] == -1)                ans[i] = e[i].l;            printf("%d", ans[i]);            if (i == m + k - 1)                puts("");            else                printf(" ");        }        return 0;    }    puts("LOSE");    return 0;}

 


联系
我们