AT_abc422_f [ABC422F] Eat and Ride 题解

AT_abc422_f [ABC422F] Eat and Ride 题解

前言

好消息：场切了。

坏消息：没开 rated。

思路

注意到数据范围非常小，考虑暴力bfs。

设 $dis_i$ 为到达第 $i$ 个点的最小燃料，$w_i$ 为到达第 $i$ 个点时耗燃料最少时的体重。

如果有一条路径到达第 $i$ 个点时已经用了 $d$ 燃料，当前体重为 $w$，如果_{有个人比你年轻还比你强} $d > dis_i$ 且 $w>w_i$，即为用的燃料不是最少的，体重还超标，那么这条路径显然不如到达这个点的最短路，所以直接丢掉，否则需要保留。

同理可得，设 $w2_i$ 为到达当前点最小的体重，$dis2_i$ 为到达当前点体重最小时用的燃料，接下来就和上文一样，如果_{有个人比你年轻还比你强} $d > dis2_i$ 且 $w>w2_i$，即为体重不是最小的，用的燃料还超标，那么这条路径显然不如到达当前点最小的体重的路径，所以直接丢掉。

做完这两个优化后就可以轻松通过本题了，仅仅 29ms。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,c[5010];
struct N{ll y,v,w;
};
vector<int> e[5010];
ll dis[5010],w[5010],dis2[5010],w2[5010];
int main(){ios::sync_with_stdio(0);cin.tie(0);cin>>n>>m;for(int i=1;i<=n;i++)cin>>c[i];for(int i=1,x,y;i<=m;i++){cin>>x>>y;e[x].push_back(y);//建图 e[y].push_back(x);}queue<N> q;memset(dis,0x3f,sizeof(dis));//初始化 memset(w2,0x3f,sizeof(w2));q.push({1,0,c[1]});while(!q.empty()){//bfsN t=q.front();q.pop();if(dis[t.y]>t.v){//如果这条路径更短 dis[t.y]=t.v;w[t.y]=t.w;}if(w2[t.y]>t.w){//如果当前体重更小 w2[t.y]=t.w;dis2[t.y]=t.v;}else if((dis[t.y]<t.v&&w[t.y]<t.w)||(dis2[t.y]<t.v&&w2[t.y]<t.w))continue;//舍去无用路径 for(int y:e[t.y]){q.push({y,t.v+t.w,t.w+c[y]});}}for(int i=1;i<=n;i++){cout<<dis[i]<<'\n';}return 0;
}