【NOIP2019模拟2019.11.13】旅行 && GDKOI2018 还念（二分答案+dij）

Description：

题解：

显然满足二分性。

并且每一条边要不选l要不选r。

二分的那条链肯定要选l。

考虑有两个人在走最短路，一个人一开始必须走二分的那条链，要求第一个人走的比第二个人快。

安排的话也比较简单，第一人先走到这条边就给l，第二个人就给r。

还有一种想法，先只给二分的链l，其它都给r，跑一遍最短路，设为dis1。

然后再从二分的链的结尾开始，每条边都设为l，跑最短路，dis2。

然后一个点x的dis2[x]+二分的链长<=dis1[x]，那么就可以走这个点，否则不能走，最后看能不能走到终点。

两个做法本质有一点点相似。

Code：

#include<bits/stdc++.h>
#define fo(i, x, y) for(int i = x, B = y; i <= B; i ++)
#define ff(i, x, y) for(int i = x, B = y; i <  B; i ++)
#define fd(i, x, y) for(int i = x, B = y; i >= B; i --)
#define ll long long
#define pp printf
#define hh pp("\n")
using namespace std;

const int N = 2e5 +5;

int n, m, p, b[N];

struct edge {
    int x, y, l, r;
} a[N];
    
int fi[N], nt[N], to[N], tot;
void link(int x, int y) {
    nt[++ tot] = fi[x], to[tot] = y, fi[x] = tot;
}

struct P {
    int x; ll y;
    P(int _x = 0, ll _y = 0) {
        x = _x, y = _y;
    }
};

bool operator < (P a, P b) {
    return a.y > b.y;
}

priority_queue<P> q;

int ky[N];
ll dis[N], dis2[N];
int us[N][2];

int pd(int mi) {
    fo(i, 1, n) fo(j, 0, 1) us[i][j] = 0;
    fo(i, 1, m) ky[i] = 0;
    fo(i, 1, mi) ky[b[i]] = 1;
    fo(i, 1, n) dis[i] = dis2[i] = 1e18;
    ll sb = 0; dis[1] = 0;
    fo(i, 1, mi) {
        sb += 2 * a[b[i]].l;
        dis[a[b[i]].y] = sb;
        if(i < mi && a[b[i]].y == 2) return 0;
    }
    q.push(P(a[b[mi]].y, sb));
    dis2[1] = 1; q.push(P(1, 1));
    while(q.size()) {
        P b;
        while(q.size()) {
            b = q.top(); q.pop();
            if(us[b.x][b.y & 1]) continue;
            break;
        }
        if(us[b.x][b.y & 1]) continue;
        us[b.x][b.y & 1] = 1;
        for(int i = fi[b.x]; i; i = nt[i]) {
            int y = to[i];
            ll z = b.y;
            if(!ky[i]) ky[i] = (b.y & 1) + 1;
            z += ky[i] == 1 ? a[i].l * 2 : a[i].r * 2;
            if(b.y & 1) {
                if(z < dis2[y]) {
                    dis2[y] = z;
                    q.push(P(y, dis2[y]));
                }
            } else {
                if(z < dis[y]) {
                    dis[y] = z;
                    q.push(P(y, dis[y]));
                }
            }
        }
    }
    return dis[2] <= dis2[2];
}

int main() {
    freopen("travel.in", "r", stdin);
    freopen("travel.out", "w", stdout);
    scanf("%d %d %d", &n, &m, &p);
    fo(i, 1, m) {
        scanf("%d %d %d %d", &a[i].x, &a[i].y, &a[i].l, &a[i].r);
        link(a[i].x, a[i].y);
    }
    fo(i, 1, p) scanf("%d", &b[i]);
    int as = 0;
    for(int l = 1, r = p; l <= r; ) {
        int mi = l + r >> 1;
        if(pd(mi)) l = mi + 1; else as = mi, r = mi - 1;
    }
    if(as == 0) pp("No Response!\n"); else pp("%d\n", b[as]);
}

【NOIP2019模拟2019.11.13】旅行 && GDKOI2018 还念（二分答案+dij）

原文：https://www.cnblogs.com/coldchair/p/11852174.html