自动搬运

查看原文

来自洛谷，原作者为

	Soul_Love 这个家伙很懒，什么都留下了

搬运于2025-08-24 22:04:13，当前版本为作者最后更新于2023-08-17 17:44:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

暴力

先考虑暴力，可以用各种奇怪的算法跑出起点 $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;
}