[NHSPC 2025] 电动车充电规划问题

Tairitempest · 2026-03-06 18:45:37 · 题解

观察到题目的数据范围：边有负权，O(NM) 可行，考虑进行一个形如 Bellman-Ford 的最长路。

如果没有加油站的话直接按照题意跑一遍求最长路即可——题目说没有正环，所以不需要判。

如果直接能到终点那自然是最好的，代价直接为 0。如果到不了的话，那就要用加油站。

加油站只能使用一次，枚举加油站二分计算最小代价的时间复杂度明显不可接受，因此可以考虑计算所有加油站跑到终点最少需要多少油。这个直接建反图再跑一次即可。最后枚举所有加油站即可。

::::success[Code]

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,s,t,B,b;
ll g,p[1010];
vector< pair<ll,ll> > E[1010];
vector< pair<ll,ll> > rE[1010];

ll cur[1010],nd[1010];
queue<ll> q;

int main(){
    cin>>n>>m>>s>>t>>B>>b;
    for(int i=1;i<=m;i++){
        ll u,v,w;
        cin>>u>>v>>w;
        E[u].push_back({v,w});
        rE[v].push_back({u,w});
    }
    for(int i=1;i<=n;i++) cur[i]=-2e9-7;
    for(int i=1;i<=n;i++) nd[i]=2e9+7;
    cur[s]=b;nd[t]=0;
    q.push(s);
    while(q.size()){
        ll p=q.front();q.pop();
        for(auto i:E[p]){
            ll newcur=min(B,cur[p]+i.second);
            if(newcur<0) continue;
            if(newcur>cur[i.first]){
                cur[i.first]=newcur;
                q.push(i.first);
            }
        }
    }
    q.push(t);
    while(q.size()){
        ll p=q.front();q.pop();
        for(auto i:rE[p]){
            ll newcur=max(0ll,nd[p]-i.second);
            if(newcur>B) continue;
            if(newcur<nd[i.first]){
                nd[i.first]=newcur;
                q.push(i.first);
            }
        }
    }
    ll ans=1e9+7;
    cin>>g;
    for(int i=1;i<=g;i++){
        cin>>p[i];
        ans=min(ans,max(0ll,nd[p[i]]-cur[p[i]]));
    }
    if(cur[t]>=0) ans=0;
    if(ans<1e9+7) cout<<ans<<endl;
    else cout<<-1<<endl;
    return 0;
}

::::