本文主要是介绍POJ-3635-Full Tank?-spfa+ 优先队列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一开始想用DP做的，后来想了想，用DP的肯定会超时。
然后想用dij跑图就可以了，然后再加上优先队列优化。
没到达一个点的时候，有两种选择，一种是一点油都不加，然后往后跑。
另外一种就是加一升的油。
用优先队列选择最优的子结果。
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
using namespace std;
#define maxeg 10000
#define maxpt 1100
#define INF 99999999
struct lists
{int u;int v;int w;int next;
}node[maxeg*2+100];
int head[maxpt];
int nums;
void init()
{memset(head,-1,sizeof(head));nums=0;
}
void add(int u,int v,int w)
{node[nums].u=u;node[nums].v=v;node[nums].w=w;node[nums].next=head[u];head[u]=nums++;
}
int vals[maxpt];
int n,m;
int d[maxpt][maxpt];
struct ns
{int x;int cc;int val;friend bool operator < (ns a,ns b){return a.val>b.val;}
}p,q;
priority_queue<ns>que;
void spfa(int cc,int st,int ed)
{int i,j;for(i=0;i<=n;i++){for(j=0;j<=cc;j++)d[i][j]=INF;}d[st][0]=0;while(!que.empty())que.pop();p.cc=0;p.x=st;p.val=0;que.push(p);while(!que.empty()){q=que.top();que.pop();int u=q.x;int c=q.cc;int vv=q.val;// cout<<u<<" "<<c<<" "<<vv<<endl;if(u==ed)break;//if(u==ed)continue;for(i=head[u];i!=-1;i=node[i].next){int v=node[i].v;int w=node[i].w;if(c>=w){int yu=c-w;if(d[v][yu]>d[u][c]){d[v][yu]=d[u][c];p.x=v;p.cc=yu;p.val=d[v][yu];que.push(p);}}}if(c<cc){p.x=q.x;p.cc=q.cc+1;p.val=q.val+vals[u];if(d[u][p.cc]>p.val){d[u][p.cc]=p.val;que.push(p);}}}int ans=INF;for(i=0;i<=cc;i++){ans=min(d[ed][i],ans);}if(ans!=INF)cout<<ans<<endl;else cout<<"impossible"<<endl;
}
int main()
{int i,a,b,c,q,s,t;cin>>n>>m;for(i=0;i<n;i++)scanf("%d",&vals[i]);init();while(m--){scanf("%d%d%d",&a,&b,&c);add(a,b,c);add(b,a,c);}scanf("%d",&q);while(q--){scanf("%d%d%d",&c,&s,&t);spfa(c,s,t);}return 0;
}
这篇关于POJ-3635-Full Tank?-spfa+ 优先队列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
