CF843D-Dynamic-ShortestPath(动态最短路)

动态最短路：CF843D Dynamic Shortest Path

题意：
有一张\(n\)个点\(m\)条边的有向带权图，\(q\)次询问：

1 \(1 v\) 询问从\(1\)到\(v\)的最短路，无解输-\(1\)

2 \(c\ l_1\ l_2\ ...\ l_c\ l_i\)的边权增加\(1\)

\(q \leqslant 2000 n,m \leqslant 10^5\)

题解：

暴力\(dij\)显然过不了，需要优化

首先我们知道一种\(dij\)的优化方法：
保证边权都为正，且边权和不超过\(W\)的时候

性质：如果用 \(??\) 更新周围的点 \(??\) 的最短路，那么
源到 \(t\) 的最短路长度一定大于到 \(??\) 的最短路长度。

用\(0\)~\(W\) 的(桶)队列代替堆

从小到大枚举值来取出当前最小值。根据性质，加
入的元素一定只会加到当前枚举的这个值的后面。

复杂度\(O(m+W)\)，现在我们要尽量缩小值域就可以优化了

先做一遍正常\(dij\)，然后考虑该边若干条边造成的影响

令每条边\((x,y)\)的边权为\(dis[x]+edge[i]-dis[y]\),

假设这样求出来的最短路为\(f[x]\)，则\(f[x]\)表示新图中此点的距离较原图的增量

分析\(f[x]\)的值域：一次更新\(c\)条边，则最短路最多增加\(c\)，\(n\)个点的最短路共经过\(n-1\)条边，
则最短路增加不超过\(n-1\),而\(n\)的范围是\(10^5\)，就可以接受了，总共复杂度\(O(q(m+W))\)

//CF843D-Dynamic-ShortestPath
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <queue>
using namespace std;

typedef long long LL;
#define cls(x) memset(x,0,sizeof(x))
#define For(i,j,k) for(register int i=(j);i<=(k);++i)
#define Rep(i,j,k) for(register int i=(j);i>=(k);--i)
#define rint register int
#define il inline

il int read(int x=0,int f=1,char ch='0')
{
    while(!isdigit(ch=getchar())) if(ch=='-') f=-1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    return f*x;
}

const int N=1e5+5;
int head[N],ver[N],nxt[N],edge[N];
int n,m,Q,tot;
LL d[N],f[N],t; bool v[N];
il void add(int x,int y,int z)
{ ver[++tot]=y; nxt[tot]=head[x]; head[x]=tot; edge[tot]=z; }

il void dij()
{
    priority_queue<pair<LL,int> > q; 
    memset(d,0x3f,sizeof(d)); d[1]=0;
    q.push(make_pair(0,1));
    while(q.size())
    {
        int x=q.top().second; q.pop();
        if(v[x]) continue; v[x]=1;
        for(rint i=head[x];i;i=nxt[i])
        {
            int y=ver[i]; if(d[y]<=d[x]+edge[i]) continue;
            d[y]=d[x]+edge[i]; q.push(make_pair(-d[y],y));
        }
    }
}

queue<int> q[N];
il void work(int maxn)
{
    memset(f,0x3f,sizeof(f)); 
    f[1]=0; q[0].push(1);
    for(rint now=0;now<=t;++now) while(q[now].size())
    {
        int x=q[now].front(); q[now].pop(); if(f[x]<now) continue;
        //一个点可能被插入多个队列中
        for(rint i=head[x];i;i=nxt[i])
        {
            int y=ver[i],z=d[x]+edge[i]-d[y];
            if(f[y]<=f[x]+z) continue;
            f[y]=f[x]+z; if(f[y]>maxn) continue;
            q[f[y]].push(y); t=max(t,f[y]);
        }
    }
    For(i,1,n) d[i]=min(d[0],d[i]+f[i]);
}

int main()
{
    n=read(); m=read(); Q=read();
    For(i,1,m) { int x=read(),y=read(),z=read(); add(x,y,z); }
    dij();
    while(Q--)
    {
        int op=read();
        if(op==1)
        {
            int x=read();
            printf("%lld\n",d[x]>=d[0]?-1:d[x]);
        }
        else
        {
            int c=read(),k; For(i,1,c) k=read(),++edge[k];
            work(min(c,n-1));
        }
    }
    return 0;
}