神秘最短路 CF843D Dynamic Shortest Path

xfrvq · 2024-10-14 07:47:58 · 题解

每次修改都跑 \tt dijkstra，复杂度 O\left(q(n+m)\log n\right)，少个 \log 可以通过。

注意到 \tt dijkstra 的 \log 复杂度来自于堆，如果不用堆而是对 dis 的值域开 \tt queue，枚举小值域向大值域转移，复杂度 O(V+n+m)。

于是设每一轮 dis 的增加量为 \Delta，0\le\Delta\le c（c 条边每条至多贡献一次）。正常转移是 dis_v\gets dis_u+w，这里 dis_v+\Delta_v\gets dis_u+\Delta_u+w，即 \Delta_v\gets dis_u+\Delta_u-dis_v+w。

代入 V=c，总复杂度 O((n+m)\log n+q(n+m))。

代码使用 __gnu_pbds 配对堆，可让 \tt dijkstra 做到 O(n\log n+m)。

#include<bits/stdc++.h>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;

#ifdef ONLINE_JUDGE
static char buf[16777216],*p1=buf,*p2=buf;
#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,16777216,stdin),p1==p2)?EOF:*p1++
#endif

inline int read(){
    register int x = 0;
    register char c = getchar();
    for(;c < '0' || c > '9';c = getchar());
    for(;c >= '0' && c <= '9';c = getchar())
        x = x * 10 + (c ^ '0');
    return x;
}

using ll = long long;
using pq = __gnu_pbds::priority_queue<pair<ll,int>,greater<>,__gnu_pbds::pairing_heap_tag>;

const int N = 1e5 + 5;

int n,m,q,k,w[N],dlt[N];
ll dis[N];
vector<pair<int,int>> G[N];
queue<int> V[N];
pq Q; pq::point_iterator P[N];

void dij(){
    for(int i = 1;i <= n;++i)
        P[i] = Q.push({dis[i] = i == 1 ? 0 : 1e18,i});
    while(Q.size() && Q.top().first < 1e18){
        auto[d,u] = Q.top(); Q.pop();
        for(auto[v,i] : G[u])
            if(dis[v] > dis[u] + w[i])
                Q.modify(P[v],{dis[v] = dis[u] + w[i],v});
    }
    for(int i = 1;i <= n;++i) if(dis[i] == 1e18) dis[i] = -1;
}

void dij1(){
    for(int i = 2;i <= n;++i) dlt[i] = k + 1;
    V[0].push(1);
    for(int d = 0;d <= k;++d)
        while(V[d].size()){
            int u = V[d].front(); V[d].pop();
            if(dlt[u] != d) continue;
            for(auto[v,i] : G[u])
                if(dlt[v] > dis[u] + w[i] - dis[v] + dlt[u])
                    V[dlt[v] = dis[u] + w[i] - dis[v] + dlt[u]].push(v);
        }
    for(int i = 1;i <= n;++i) if(dlt[i] < k + 1) dis[i] += dlt[i];
}

int main(){
    n = read(),m = read(),q = read();
    for(int i = 1,u,v;i <= m;++i)
        u = read(),v = read(),w[i] = read(),G[u].emplace_back(v,i);
    for(dij();q--;){
        if(read() == 2){
            for(int i = k = read();i--;) ++w[read()];
            dij1();
        } else printf("%lld\n",dis[read()]);
    }
    return 0;
}