CF360E

lahlah · 2021-08-13 16:17:14 · 题解

貌似被 hack 了一车人

写一个貌似是对的题解吧

首先发现边权只有最大最小是有用的

考虑从 s_1,s_2 同时出发跑 dijkstra

对于第一个人，我们希望他的边权尽量为 L_i ，第二个人的尽量为 R_i

可以发现如果两个人的最优路径都到了点 u ,那 u 之后一段应该是完全一样的

因为只用考虑胜负平，所以看是谁先进来的即可

分两种情况考虑，

• 要赢：我们让同时到的点的边尽量大，让 s_1 可以通过另外一条路先到达 t
• 要平手：让同时到的点的边权尽量小，尽量避免 s_2 通过另外一条路先到达 t

否则就是 LOSE

然后特判一下 s1=s2 即可

前m条边就当成 L=R 的来做

时间复杂度与 k 无关

code:

#include<bits/stdc++.h>
#define N 200050
#define ll long long
#define pi pair<ll, int>
#define mp make_pair
using namespace std;
struct edge {
    int v, c, mi, ma, nxt;
} e[N << 1];
int p[N], eid;
void init() {
    memset(p, - 1, sizeof p);
    eid = 0;
}
void insert(int u, int v, int mi, int ma) {
    e[eid].v = v;
    e[eid].mi = mi;
    e[eid].ma = ma;
    e[eid].nxt = p[u];
    p[u] = eid ++;
}
const ll INF = 1e18;
priority_queue<pi, vector<pi>, greater<pi> > q;
ll dis[N];
int vis[N], bel[N], s1, s2, t, n, m, k;
void dij(int o) {
    for(int i = 0; i <= n; i ++) dis[i] = INF, vis[i] = 0,
    dis[s1] = dis[s2] = 0; bel[s1] = 1, bel[s2] = 2;
    q.push(mp(0, s1)), q.push(mp(0, s2));
    while(q.size()) {
        int u = q.top().second; q.pop();
        if(vis[u]) continue;
        vis[u] = 1;
        for(int i = p[u]; i + 1; i = e[i].nxt) {
            if(bel[u] == 1) e[i].c = e[i].mi; else e[i].c = e[i].ma;
            int v = e[i].v, c = e[i].c;
            if(o) {
                if(bel[u] == 1) {
                    if(dis[v] > dis[u] + c) dis[v] = dis[u] + c, bel[v] = 1, q.push(mp(dis[v], v));
                }
                else {
                    if(dis[v] >= dis[u] + c) dis[v] = dis[u] + c, bel[v] = 2, q.push(mp(dis[v], v));
                }

            } else {
                if(bel[u] == 1) {
                    if(dis[v] >= dis[u] + c) bel[v] = 1, dis[v] = dis[u] + c, q.push(mp(dis[v], v));
                }
                else {
                    if(dis[v] > dis[u] + c) bel[v] = 2, dis[v] = dis[u] + c, q.push(mp(dis[v], v));
                }
            }
        }
    }
    if(bel[t] == 2) return ;
    if(o) printf("WIN\n"); else printf("DRAW\n");
    for(int i = k; i < eid; i ++) printf("%d ", max(e[i].c, e[i].mi));
    exit(0);
}
int main() {
    init();
    scanf("%d%d%d", &n, &k, &m);
    scanf("%d%d%d", &s1, &s2, &t);
    for(int i = 1; i <= k; i ++) {
        int u, v, l;
        scanf("%d%d%d", &u, &v, &l);
        insert(u, v, l, l);
    }//前k条边就当成l=r的情况
    for(int i = 1; i <= m; i ++) {
        int u, v, l, r;
        scanf("%d%d%d%d", &u, &v, &l, &r);
        insert(u, v, l, r);
    }
    if(s1 == s2) {printf("DRAW\n"); for(int i = k; i < eid; i ++) printf("%d ", e[i].mi); return 0; }
    dij(1), dij(0), printf("LOSE");//先跑要赢的，再跑要平的
    return 0;
}