[CF 1163 F] Indecisive Taxi Fee

CF 1163 F

设其中随意一条最短路的边集为$E$,可以分为四种情况考虑

  1. $x < w_t, t\in E$或$x > w_t, t\not \in E$,则最短路依然是$E$
  2. $x < w_t, t\not \in E$,则最短路是$E$和经过$t$的最短路取个$\min$
  3. $x > w_t, t\in E$,则最短路是$E$和不经过$t$的最短路取$min$

要求出经过$t$的最短路,只需要求出$1$到各点的距离$d1$和$n$到各点的距离$dn$,然后经过$t$的最短路就是$\min\{d1_{x_t}+dn_{y_t}, d1_{y_t}+dn_{x_t}\} + w_t$

对于不经过$t$的最短路,一定是和$E$有一段前缀和一段后缀相同的(前缀后缀均可以为空)。设$l_{i}$为从$1$到$i$的最短路和$E$的最短前缀,$r_{i}$为从$i$到$n$的最短路与$E$的最短后缀。对于边$t$,如果不经过的边属于$[l_{x_t}, r_{y_{t}}]$的话,都可以走$1\to x_{t}\to y_{t}\to N$这条线,所以线段树维护一下不走每个边的最短路长度就行了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <unordered_map>

#define X first
#define Y second
#define mp std::make_pair
#define MAX_N 200010
#define inf 0x3f3f3f3f3f3f3f3f
typedef long long ll;
typedef std::pair<ll, int> pli;

struct Data{
    int x, y, z;
    Data(){}
    Data(int x, int y, int z) : x(x), y(y), z(z){}
}a[MAX_N];

struct Graph{
    int to[MAX_N << 1], ne[MAX_N << 1], w[MAX_N << 1], head[MAX_N], cnt;
    Graph() : cnt(1){}
    void add_edge(int x, int y, int z){
        to[++cnt] = y, ne[cnt] = head[x], w[cnt] = z, head[x] = cnt;
        to[++cnt] = x, ne[cnt] = head[y], w[cnt] = z, head[y] = cnt;
    }
    int operator [](int x){
        return head[x];
    }
}G;

int N, M, Q, lp[MAX_N], rp[MAX_N], id[MAX_N], pre[MAX_N];
ll dis1[MAX_N], disn[MAX_N], cnt1[MAX_N], cntn[MAX_N];
bool vis[MAX_N], fl[MAX_N];
std::priority_queue <pli> q;
std::unordered_map <int, std::unordered_map<int, int> > dis;

void work1(int x, int y, int idx){
    pre[y] = idx;
}

void work2(int x, int y, int idx){
    if(!fl[y]) lp[y] = lp[x];
    cnt1[y] += cnt1[x];
}

void work3(int x, int y, int idx){
    if(!fl[y]) rp[y] = rp[x];
    cntn[y] += cntn[x];
}

template <void (*func)(int, int, int)>
void dij(int S, ll *dis){
    memset(dis, 0x3f, sizeof(dis1));
    memset(vis, 0, sizeof(vis));
    dis[S] = 0;
    q.push(mp(0, S));
    while(!q.empty()){
        int x = q.top().Y; q.pop();
        if(vis[x]) continue;
        vis[x] = true;
        for(int i = G[x]; i; i = G.ne[i])
            if(dis[G.to[i]] > dis[x] + G.w[i]){
                func(x, G.to[i], i);
                dis[G.to[i]] = dis[x] + G.w[i];
                q.push(mp(-dis[G.to[i]], G.to[i]));
            }
    }
}

namespace Seg{
    #define mid ((l + r) >> 1)
    #define ls (v << 1)
    #define rs (v << 1 | 1)
    ll mn[MAX_N << 2], tag[MAX_N << 2];

    void push_down(int v){
        mn[ls] = std::min(mn[ls], tag[v]);
        tag[ls] = std::min(tag[ls], tag[v]);
        mn[rs] = std::min(mn[rs], tag[v]);
        tag[rs] = std::min(tag[rs], tag[v]);
        tag[v] = inf;
    }

    void push_up(int v){
        mn[v] = std::min(mn[ls], mn[rs]);
    }

    void modify(int v, int l, int r, int ql, int qr, ll val){
        if(ql > qr) return;
        if(ql <= l && r <= qr){
            tag[v] = std::min(tag[v], val);
            mn[v] = std::min(mn[v], val);
            return;
        }
        push_down(v);
        if(ql <= mid) modify(ls, l, mid, ql, qr, val);
        if(qr > mid)  modify(rs, mid + 1, r, ql, qr, val);
        push_up(v);
    }

    ll query(int l, int r, int p){
        int v = 1;
        while(l < r){
            push_down(v);
            if(p <= mid) v = ls, r = mid;
            else l = mid + 1, v = rs;
        }
        return mn[v];
    }
}

int main(){
    memset(lp, -1, sizeof(lp));
    memset(rp, -1, sizeof(rp));
    memset(Seg::mn, 0x3f, sizeof(Seg::mn));
    memset(Seg::tag, 0x3f, sizeof(Seg::tag));
    int x, y, z;
    scanf("%d%d%d", &N, &M, &Q);
    for(int i = 1; i <= M; i++){
        scanf("%d%d%d", &x, &y, &z);
        G.add_edge(x, y, z);
        a[i] = Data(x, y, z);
        dis[x][y] = dis[y][x] = z;
    }
    dij <work1> (1, dis1); 
    int tot = 0;
    for(int i = pre[N], p = N; pre[p]; i = pre[p]){
        id[i >> 1] = ++tot;
        lp[p] = tot; fl[p] = true;
        p ^= a[i >> 1].x ^ a[i >> 1].y;
        rp[p] = tot; fl[p] = true;
    }
    lp[1] = tot + 1, rp[N] = 0;
    dij <work2> (1, dis1);
    dij <work3> (N, disn);
    for(int i = 1; i <= M; i++) if(!id[i]){
        Seg::modify(1, 1, tot, rp[a[i].y] + 1, lp[a[i].x] - 1, dis1[a[i].x] + disn[a[i].y] + a[i].z);
        Seg::modify(1, 1, tot, rp[a[i].x] + 1, lp[a[i].y] - 1, dis1[a[i].y] + disn[a[i].x] + a[i].z);
    }
    while(Q--){
        scanf("%d%d", &x, &y);
        ll ans = dis1[a[x].x] + disn[a[x].y] + y;
        ans = std::min(ans, dis1[a[x].y] + disn[a[x].x] + y);
        if(a[x].z >= y){
            if(!id[x]) ans = std::min(ans, dis1[N]);
            printf("%I64d\n", ans);
        }else{
            if(!id[x]) printf("%I64d\n", dis1[N]);
            else{
                ans = std::min(ans, Seg::query(1, tot, id[x]));
                printf("%I64d\n", ans);
            }
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注