【题目】
Travel
【...】
题意：一个初始状态为可穿越距离为0可飞行次数为0的太空飞船，每次升级花费c，提高d可穿越距离，增加e次可飞行次数，有n个星球和m条连接不同星球的路，输出从星球1到n需要最少的升级次数。不可到达则输出-1.
思路：spfa算法。
【代码】
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+10; const int inf=0x3f3f3f3f; int head[N<<2]; struct ac{ int to,next; long long di; }edge[N<<2]; int cnt; void addedge(int from,int to,ll di) { edge[cnt].to=to; edge[cnt].di=di; edge[cnt].next=head[from]; head[from]=cnt++; } ll dis[N]; bool vis[N]; int n,m; struct node{ int num; ll _dis,t; }point[N]; ll c,d,e; bool flag; void spfa() { for(int i=1;i<=n;i++) dis[i]=(ll)inf; memset(vis,false,sizeof(vis)); dis[1]=0; queue <int> Q; Q.push(1); vis[1]=true; point[1].num=point[1]._dis=point[1].t=0; while(!Q.empty()){ int u=Q.front(); Q.pop(); vis[u]=false; if(u==n) flag=true; for(int i=head[u];i!=-1;i=edge[i].next){ int to=edge[i].to; ll w=edge[i].di; ll dis_t=point[u]._dis; int num_t=point[u].num; ll t=point[u].t; if(w>dis_t){ int tt=(w-dis_t)/d; if(d!=1&&(w-dis_t)%d) tt++; dis_t+=tt*d; num_t+=tt*e; t+=tt; } if(num_t==0){ num_t+=e; dis_t+=d; t++; } if(dis[to]>t){ dis[to]=t; point[to].num=--num_t; point[to]._dis=dis_t; point[to].t=t; if(!vis[to]){ vis[to]=true; Q.push(to); } } } } } int main() { memset(head,-1,sizeof(head)); scanf("%d%d",&n,&m); scanf("%lld%lld%lld",&c,&d,&e); for(int i=1;i<=m;i++){ int a,b; ll c; scanf("%d %d %lld",&a,&b,&c); addedge(a,b,c),addedge(b,a,c); } spfa(); if(!flag) printf("-1\n"); else printf("%lld\n",dis[n]*c); return 0; }
