原题网址
这题是单源最短路的变形，题中需要维护两个量，到达结点i的步数，到达结点i的等级。用dijikstra 算法时每个节点先比较飞船等级，保留较低等级。等级相同再比较到达i的步数，保留步数较少的。最后更新i处的值。我在这使用cla[100005] ，dis[100005]维护i处的飞船等级和到达i的步数。 注意dijikstra算法要优化，否则超时。可以定义结构体，重载运算符，再用priority_queue优化。 代码如下：
#include <iostream> #include <cstdio> #include <cmath> #include <set> #include <string> #include <queue> #include <map> #include <vector> #include <cstring> #include <algorithm> #include <sstream> #define INF 107801 #define MAXN 2e5+9 #define __maxNodes 1005 const long long mod=1e6+3; using namespace std; struct Edge{ int from,to; int w; }; vector<Edge> vec[100005]; int n,m; int dis[100005],vis[100005]; //int cp[100005]; int cla[100005]; int d,c1,e; int ans; struct point{ int u; bool operator < (const point op) const{ if(cla[u]>cla[op.u]) return true; else if(cla[u]==cla[op.u] && dis[u]>dis[op.u]) return true; else return false; } }; priority_queue<point> q; void dijk() { while (!q.empty()) { point we=q.top(); q.pop();//cout << we.u << endl; for(int i=0;i<vec[we.u].size();i++) { Edge ed=vec[we.u][i]; int c,st=we.u; if(vis[ed.to]) continue; else vis[st]=1; if(cla[st]*d<ed.w || cla[st]*e<=dis[st]) { if(cla[st]*d<ed.w) { c=(ed.w-1)/d+1; } else { c=cla[st]+1; } } else c=cla[st]; if(c>cla[ed.to]) continue; else if(c==cla[ed.to] && dis[ed.to]<=dis[st]+1) continue; else { cla[ed.to]=c; dis[ed.to]=dis[st]+1; } point ne;//cout << ne.u << endl; ne.u=ed.to; q.push(ne); } } } int main() { scanf("%d%d",&n,&m); int i; Edge e1,e2; for(i=0;i<=n;i++) vec[i].clear(); scanf("%d%d%d",&c1,&d,&e); for(i=0;i<m;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); e1.from=x;e1.to=y;e1.w=z; e2.from=y;e2.to=x;e2.w=z; vec[x].push_back(e1); vec[y].push_back(e2); } //ans=INF; memset(dis,INF,sizeof(dis)); memset(vis,0,sizeof(vis)); memset(cla,INF,sizeof(cla)); //cout << dis[0] << endl; dis[1]=0;cla[1]=0;vis[1]=1; point s;s.u=1;q.push(s); dijk(); //dfs(1,n); printf("%d\n",cla[n]*c1); return 0; }