题解：P9126 [USACO23FEB] Moo Route II S

hqc20230131 · 2026-10-23 17:33:10 · 题解

设 dis_u 表示来到 u 的最早时间，a_u 为每个机场的停留时间，所以我们利用 Dijkstra 算法遍历整一张图。假如 u 能够到达 v，并且航班起飞、降落时间分别为 s 和 t，那么当 s\ge dis_u+a_u 时，dis_u 可以对 dis_v 进行松弛操作，即当 dis_v>t 时，进行 dis_v=t。

这样的 Dijkstra 是不会有负环的，因为 dis_u 不会一直变小。但是这样写出来的代码只有 65 分。

接下来的优化其实比较简单，有贪心的意思。我们把每一个点能够到达的边按照结束时间降序排序，跳过一些走过的边。

最后注意输出 -1 的情况，以及一些优化。

:::success[Dijkstra 的代码]

#include<bits/stdc++.h>
#define N 200005
using namespace std;

struct edge
{
    int to,s,t;
    bool operator < (const edge &k)const
    {
        return (s^k.s)?(s>k.s):(t<k.t);
    }
};
int n,m,a[N],dis[N],tag[N],inq[N];
vector<edge> g[N];// 注意链式前向星难以对边进行排序，故使用邻接表

void dij()
{
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
    for(int i=1;i<=n;i++)dis[i]=tag[i]=1e9+1;
    dis[1]=-a[1];// 思考为什么令 dis[1] 为负数
    q.push({-a[1],1});
    inq[1]=1;
    while(!q.empty())
    {
        int u=q.top().second;
        q.pop();
        inq[u]=0;
        if(tag[u]==dis[u])continue;
        tag[u]=dis[u];
        for(auto [v,s,t]:g[u])
        {
            if(s>=dis[u]+a[u]&&dis[v]>t)
            {
                dis[v]=t;
                if(!inq[v])
                    q.push({dis[v],v}),inq[v]=1;
            }
        }
    }
}

int main()
{
//  freopen("sample.in","r",stdin);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1,u,v,s,t;i<=m;i++)
    {
        cin>>u>>s>>v>>t;
        g[u].push_back({v,s,t});
    }
    for(int i=1;i<=n;i++)sort(g[i].begin(),g[i].end());
    for(int i=1;i<=n;i++)cin>>a[i];
    dij();
    cout<<0<<'\n';
    for(int i=2;i<=n;i++)cout<<(dis[i]==1e9+1?-1:dis[i])<<'\n';
    return 0;
}

:::