P5872 [SEERC2018]Rabbit vs Turtle 题解

· · 题解

这篇题解应该不会过审。

题意

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

懒得简述了。

题解

直接从 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";
}
/*

*/