题目链接：https://nanti.jisuanke.com/t/39280
题目大意：有n个星球m条传送通道，每条传送通道有长度，Alice要驾驶飞船从星球1飞到星球n，飞船初始等级为0，每升一级增加传送次数e和传送距离d，如果传送通道的长度大于飞船当前的传送距离飞船就没法飞过去，得升级，或者是传送次数（经过的边数）超过飞船的传送次数，也得升级。最后要求飞船从1到n需要升到的最小等级。如果无解则输出-1。
思路：一开始学弟就想到二分，结果我们都在写BFS和最短路23333，最后当我发现并不是最短路而是需要满足最大值最小这个特性时，学弟二分都快写完了233333
最后整理一下思路，到达一个点消耗的只是传送次数，所以我们可以二分这个次数寻找答案，假设当前升级次数为cnt，则传送次数为cnt*e，最大能通过的边为cnt*d，那么跑一遍BFS，判断是否能从起点到终点，并且传送次数不大于cnt，则满足要求，寻找更大小的cnt；否则，只能寻找更大的cnt。最后无解就是寻找到m+1还没有答案，就是无解啦。
代码：
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <cmath> #include <vector> #include <queue> using namespace std; const int maxn=1e5+10; const int INF=0x3f3f3f3f; typedef long long ll; ll n,m,c,d,e; struct Edge{ ll from,to; ll cost; Edge(int u,int v,ll c):from(u),to(v),cost(c){} }; vector<ll>G[maxn]; vector<Edge>edges; void init(){ for(int i=0;i<maxn;i++){ G[i].clear(); } edges.clear(); } void add_edges(ll u,ll v,ll cost){ edges.push_back(Edge(u,v,cost)); edges.push_back(Edge(v,u,cost)); int m=edges.size(); G[u].push_back(m-2); G[v].push_back(m-1); } struct Node{ ll u,cnt; Node(ll _u,ll _cnt):u(_u),cnt(_cnt){} bool operator < (const Node &rhs)const{ return cnt>rhs.cnt; } }; int vis[maxn]; int dis[maxn];//层次 bool BFS(ll aim){ memset(vis,0,sizeof(vis)); for(int i=0;i<maxn;i++)dis[i]=INF; ll len=aim*d; queue<int>Q; Q.push(1); vis[1]=1; dis[1]=0; while(Q.size()){ int u=Q.front();Q.pop(); bool flag=false; for(int i=0;i<G[u].size();i++){ Edge &e=edges[G[u][i]]; if(!vis[e.to]&&e.cost<=len){//必须要满足当前花销 Q.push(e.to); vis[e.to]=1; dis[e.to]=dis[u]+1;//表示到达e.to需要的最小等级 if(e.to==n){ flag=true; break; } } } if(flag)break; } return dis[n]<=aim*e;//判断能否到达n } //二分 ll find_ans(ll l,ll r){ while(l<=r){ ll mid=(l+r)>>1; if(!BFS(mid))l=mid+1; else r=mid-1; } return l; } int main(){ while(scanf("%lld%lld",&n,&m)!=EOF){ scanf("%lld%lld%lld",&c,&d,&e); for(ll i=1;i<=m;i++){ ll u,v,w; scanf("%lld%lld%lld",&u,&v,&w); add_edges(u,v,w); } ll ans=find_ans(1,m+1); if(ans==m+1){ puts("-1"); } else{ printf("%lld\n",ans*c); } } return 0; }
