P4814 题解

· · 题解

看到这题还没题解，于是想着和大佬搞一下。

暴力

先考虑暴力，可以用各种奇怪的算法跑出起点 S 到终点 T 的所有路径，然后把长度和 D_i 比较，若不大于，则把这个路径上的所有边打上 tag，最后遍历所有边，累加有 tag 标记的边的费用。

但是因为图是有环的，并且允许重复经过点和边，所以我一开始想用 K 短路来写，从小到大把所有路径跑出来，等路径长度大于 D_i 后直接输出。

总而言之，时间复杂度爆炸。

正解思路（？）

放弃暴力地跑出路径，而是考虑每条边是否会被打上 tag。

不妨设 dis_{i,j} 表示点 i 到点 j 的最短路径长度。

则很容易想到，对于长度为 w ，从 u 到 v 的边，只要最短的并且过这条边的路径长度不大于 D_i 的话，即 dis_{S,u}+w+dis_{T,v} \leq D_i，那么这条边一定会打上 tag。

所以我用 dijkstra 跑正反图，预处理出所有 dis_{S,u} 和 dis_{T,u}，然后将询问离线，从小到大排序。容易看出，对于在处理 D_i 中被打上 tag 的边，那么在处理 D_{i+1} 时，这些边一定也会打 tag，所以可以将 dis_{S,u}+w+dis_{T,v} 从小到大排序。

code

#include<bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f
using namespace std;
int n,m,s,h1[5001000],dis1[5001000],l1,vis[5001000],x,y,z,e,w,dis2[5001000],h2[5001000],l2,qq,ans[5001000],zjp=1;
struct node
{
    int dis,pos;
    bool operator <(const node &x)const
    {
        return x.dis<dis;
    }
};
struct abc
{
    int pos,val;
}D[5001000];
struct ljh
{
    int dis,cost;
}znx[5001000];
inline int read()
{
    int k=0,f=0;char c=getchar();
    for(;!isdigit(c);c=getchar()) f|=c=='-';
    for(;isdigit(c);c=getchar()) k=(k<<1)+(k<<3)+(c^48);
    return f?-k:k;
}
priority_queue<node> q;
struct edge
{
    int v,next,w,cost,u;
}e1[500100],e2[500100];
inline void add1(int x,int y,int z,int w)
{
    e1[++l1].v=y;
    e1[l1].u=x;
    e1[l1].w=z;
    e1[l1].cost=w;
    e1[l1].next=h1[x];
    h1[x]=l1;
}
inline void add2(int x,int y,int z,int w)
{
    e2[++l2].v=y;
    e2[l2].w=z;
    e2[l2].u=x;
    e2[l2].cost=w;
    e2[l2].next=h2[x];
    h2[x]=l2;
}
inline void d1()//模板
{
    for(int i=1;i<=n;i++) dis1[i]=inf;
    dis1[s]=0;
    q.push((node){0,s});
    while(!q.empty())
    {
        node t=q.top();
        q.pop();
        int k=t.pos;
        if(vis[k]) continue;
        vis[k]=1;
        for(int i=h1[k];i;i=e1[i].next)
        {
            if(dis1[e1[i].v]>dis1[k]+e1[i].w)
            {
                dis1[e1[i].v]=dis1[k]+e1[i].w;
                if(!vis[e1[i].v]) q.push((node){dis1[e1[i].v],e1[i].v});
            }
        }
    }
}
inline void d2()//模板
{
    for(int i=1;i<=n;i++)
    {
        dis2[i]=inf;
        vis[i]=0;
    }
    dis2[e]=0;
    q.push((node){0,e});
    while(!q.empty())
    {
        node t=q.top();
        q.pop();
        int k=t.pos;
        if(vis[k]) continue;
        vis[k]=1;
        for(int i=h2[k];i;i=e2[i].next)
        {
            if(dis2[e2[i].v]>dis2[k]+e2[i].w)
            {
                dis2[e2[i].v]=dis2[k]+e2[i].w;
                if(!vis[e2[i].v]) q.push((node){dis2[e2[i].v],e2[i].v});
            }
        }
    }
}
inline bool cmp1(abc x,abc y){return x.val<y.val;}
inline bool cmp2(ljh x,ljh y){return x.dis<y.dis;}
signed main()
{
    n=read(),m=read(),s=read(),e=read();
    for(int i=1;i<=m;i++)
    {
        x=read(),y=read(),z=read(),w=read();
        add1(x,y,z,w);
        add2(y,x,z,w);
    }
    qq=read();
    for(int i=1;i<=qq;i++)
    {
        D[i].val=read();
        D[i].pos=i;
    }
    sort(D+1,D+qq+1,cmp1);
    d1();//正图
    d2();//反图
    for(int i=1;i<=m;i++)
    {
        znx[i].dis=dis1[e1[i].u]+e1[i].w+dis2[e1[i].v];
        znx[i].cost=e1[i].cost;
    }
    sort(znx+1,znx+m+1,cmp2);//询问离线
    for(int i=1;i<=qq;i++)
    {
        ans[D[i].pos]=ans[D[i-1].pos];//先继承一定会打上 tag 的边
        while(znx[zjp].dis<=D[i].val&&zjp<=m)//如果可以加入新的边
        {
            ans[D[i].pos]+=znx[zjp].cost;
            zjp++;
        }
    }
    for(int i=1;i<=qq;i++) printf("%lld\n",ans[i]);
    return 0;
}