题解 CF843D 【Dynamic Shortest Path】

· · 题解

神仙题 神仙切 @Ctime_Pup_314 orz

有一种O(m+W)的做法(W是值域)

考虑裸的迪杰斯特拉的过程

我们每次找全局dis的最小值 然后取出这个点进行拓展

现在我们在做迪杰斯特拉的时候 对值域开一个桶 dij的时候扫过这些桶 取出最小的值进行拓展(变成了bfs)

因为相同的值有很多点 因此我们要拿一个数据结构来保存这些点(可以是vector或者queue或者链表)

对于这道题 我们可以先用普通的迪杰斯特拉跑一边最短路 记录1到每一个点的最短路dis

然后我们赋值一个新边权:对于一条边(x,y) 我们把它的边权赋值为dis[x]+e[i].w-d[y]

由于边权是只增加不减少的 所以最短路只会变大 不会变小

那么在新图上走的含义就是到这个点的距离增量

要最小化这个增量 我们就应该走一个最短路

还有一件事 给老爹倒杯茶

因为更新c条边 所以最短路对多增加c

有因为最短路的路径构成是一棵树 所以最多增加n-1

所以我们把<=min(c,n-1) 的增量加入队列

#include <iostream> 
#include <cstdio>
#include <cstring>
#include <queue>
#define il inline
#define res register int
#define ll long long
#define pa pair <ll,int>
#define mp make_pair
using namespace std;
const int N=1e5+5;
const int M=1e5+5; 
const ll inf=0x3f3f3f3f3f3f3f3f;
il int read()
{
    int x=0,f=0,c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return f?-x:x;
}
struct Edge
{
    int to,next,w;
}e[M];
int head[N],cnt;
il void add(int a,int b,int c)
{
    cnt++;
    e[cnt].to=b;e[cnt].w=c;e[cnt].next=head[a];
    head[a]=cnt; 
}
ll d[N];
bool vis[N];
int n,m,q;
ll dij(int s)
{
    priority_queue< pa > q;
    memset(d,0x3f,sizeof d);
    memset(vis,0,sizeof vis);
    d[s]=0; q.push( mp(0,s) );
    while(!q.empty())
    {
        int x=q.top().second; q.pop();
        if(vis[x]) continue;
        vis[x]=1;
        for(res i=head[x];i;i=e[i].next)
        {
            int y=e[i].to;
            if(d[y]>d[x]+e[i].w) d[y]=d[x]+e[i].w, q.push(mp(-d[y],y ));
        }
    }
}
queue<int> s[N];
ll f[N],mx;

void bfs(int c)
{
    mx=0;
    for(res i=0;i<=mx;i++)//遍历值域 更新值域
        while(!s[i].empty())
        {
            int x=s[i].front(); s[i].pop();
            if(f[x]<i) continue;
            for(res i=head[x];i;i=e[i].next)
            {
                int y=e[i].to,z=d[x]+e[i].w-d[y];
                if(f[y]>f[x]+z)
                {
                    f[y]=f[x]+z;
                    if(f[y]<=min(c,n-1))  
                    {
                        s[f[y]].push(y);
                        mx=max((ll)mx,f[y]);
                    }
                }
            }
        }
}

int main()
{
    n=read(); m=read(); q=read();
    for(res i=1;i<=m;i++) 
    {
        int x=read(),y=read(),z=read();
        add(x,y,z); 
    }
    dij(1);
//  cout<<"dfa:"<<inf<<endl;
    while(q--)
    {
        int opt=read(),c=read();
        if(opt==1) d[c]==inf?puts("-1"):printf("%I64d\n",d[c]);
        else 
        {
            for(res i=1;i<=c;i++) e[read()].w++;
            memset(f,0x3f,sizeof f);
            f[1]=0; s[0].push(1); 
            bfs(c);
            for(res i=1;i<=n;i++) d[i]=min(inf,f[i]+d[i]);
        }
    }
    return 0;
}