最短路算法_最短路问题Dijkstra算法

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3794

题意：有n个城市，标号是1~n，一个司机要从1到n，开始时车里有c的油，单向路，然后给出几个加油站，到加油站后油箱补满，无消耗，再给出几个地方可以卖掉油（只能卖一次），以及当地的价格，问司机从1到达n的时候最多挣多少钱。。

思路：分成两部分，先求起点到各个卖油点的最小花费，在求从各个卖油点到重点的最小花费，然后如果能卖就卖掉（如果中途到了加油点就将花费更新为零，还要判断是否能更新，注意任何时候都不能超过油量 c ，貌似是这里WA了几次= =）。。

代码：

#include<cstdio> #include<cstring> #include<iostream> #include<queue> #include<stack> #include<algorithm> using namespace std; const int maxn = 2200; const int maxm = ; const int inf= 0x3f3f3f3f; struct Side{int u,v,w,next;}side[maxm]; int node[maxn],top; void add_side(int u,int v,int w){ side[top]=(Side){u,v,w,node[u]}; node[u]=top++; } int n,m,c; int dist[maxn],in[maxn]; int ff,ss; int fuel[maxn],sell[maxn],use[maxn]; queue<int>q; void spfa(int a) { memset(dist,inf,sizeof(dist)); memset(in,0,sizeof(in)); dist[a]=0; q.push(a); while(!q.empty()) { int u=q.front(); q.pop(); in[u]=0; for(int i=node[u];i!=-1;i=side[i].next) { if(dist[u]+side[i].w>c)continue; int v = side[i].v; if(dist[v]>dist[u]+side[i].w){ dist[v]=dist[u]+side[i].w; if(fuel[v]==1)dist[v] = 0; if(!in[v]){ q.push(v); in[v]=1; } } } } } void build(){ int tt=top; memset(node,-1,sizeof(node)); top=0; for(int i=0;i<tt;i++) add_side(side[i].v,side[i].u,side[i].w); //for(int i=0;i<top;i++) // printf("cong %d dao %d huafei %d\n",side[i].u,side[i].v,side[i].w); } int main() { while(~scanf("%d%d%d",&n,&m,&c)) { memset(node,-1,sizeof(node)); memset(sell,0,sizeof(sell)); memset(fuel,0,sizeof(fuel)); top=0; while(m--){ int a,b,l; scanf("%d%d%d",&a,&b,&l); add_side(a,b,l); } scanf("%d",&ff); for(int i=0;i<ff;i++){ int a; scanf("%d",&a); fuel[a]=1; } scanf("%d",&ss); for(int i=0;i<ss;i++){ int a,b; scanf("%d%d",&a,&b); sell[a]=b; } spfa(1); if(dist[n]==inf){printf("-1\n");continue;} for(int i=1;i<=n;i++) use[i]=dist[i]; build(); spfa(n); int maxn = 0; for(int i=1;i<=n;i++){ if(sell[i]&&use[i]+dist[i]<c){ maxn = max(maxn,sell[i]*(c-use[i]-dist[i])); } } cout<<maxn<<endl; } return 0; }