自动搬运

查看原文

来自洛谷，原作者为

	AsunderSquall The cruelest fate is to have hope and see it crushed before your eyes.

搬运于2025-08-24 22:15:08，当前版本为作者最后更新于2021-11-03 15:14:34，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这篇题解应该不会过审。

题意

出题人的语文水平英语水平一直可以的。

懒得简述了。

题解

直接从 $n$ 号点倒着跑一遍 Dij，然后枚举兔子路径上的点是否可以开始进行作弊，同时双指针维护乌龟走到哪里了，然后 $O(1)$ 判断一下就行了。
总复杂度 $O((n+m) \log m)$。

代码

#include<bits/stdc++.h>
#define int long long
#define rd(x) x=read()
using namespace std;
const int N=5e5+5;
int read(){int x=0,f=1;char ch=getchar();while (ch>'9'||ch<'0'){if (ch=='-')f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
void write(int x){if (x<0){putchar('-');x=-x;}if (x>=10)write(x/10);putchar(x%10+'0');}

int n,m,pr,pt;
bool vis[N];
int tP[N],tS[N],rP[N];
int dis[N],sum[N];
vector<int>ans;
struct edge{int v,w;};
vector<edge> G[N];
struct Edge{int u,v,t,r;}e[N];
struct Node{int x;bool operator<(const Node &o) const{return dis[x]>dis[o.x];}};

void Dij(int S)
{
	for (int i=1;i<=n;i++) dis[i]=1e18;dis[S]=0,vis[S]=1;
	priority_queue<Node> Q;Q.push({S});
	while (!Q.empty())
	{
		Node x=Q.top();Q.pop();int u=x.x;vis[u]=0;
        for (edge e:G[u]) if (dis[e.v]>dis[u]+e.w)
        {
            dis[e.v]=dis[u]+e.w;
            if (!vis[e.v]) {vis[e.v]=1;Q.push({e.v});}
        }
	}
}

signed main()
{
    rd(n);rd(m);
	for (int i=1,u,v,t,r;i<=m;i++) rd(u),rd(v),rd(t),rd(r),G[v].push_back({u,r}),e[i]={u,v,t,r};
    rd(pt);for (int i=1;i<=pt;i++) rd(tP[i]),rd(tS[i]);
	rd(pr);for (int i=1;i<=pr;i++) rd(rP[i]);
	Dij(n);
	for (int i=pt;i>=1;i--) sum[i]=sum[i+1]+e[tP[i]].t;
	for (int i=1,j=1,cntT=0,cntR=0;i<=pr;i++)
	{
        int u=e[rP[i]].u,v=e[rP[i]].v,r=e[rP[i]].r,t=e[rP[i]].t;
		if (dis[u]==dis[v]+r){cntR+=r;continue;}
		while (j<=pt && cntT+tS[j-1]+e[tP[j]].t<=cntR){cntT+=tS[j-1]+e[tP[j]].t;j++;}
		if (cntT+tS[j-1]+sum[j]>=cntR+dis[u]) ans.push_back(u);
		cntR+=r;
	}
	sort(ans.begin(),ans.end());cout<<ans.size()<<"\n";for (int x:ans) cout<<x<<" ";cout<<"\n";
}
/*

*/