题目链接:http://poj.org/problem?id=3635
题意:有n个城市,m条双向路。给出每个城市的油价,每条路需要耗费一定的油量。有q个询问,油箱的容量为c的车,从城市s走到e,求最少的加油价格。
思路:dp[i][j]表示到达城市 i 还剩 j 油量的最小花费。用优先队列(优先最小花费)更新,即变形的dijkstra,有两个操作,加油和过路。
代码:
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #define inf 0x3f3f3f3f #include<queue> using namespace std; typedef long long ll; const int maxn=1100; const int maxm=21000; struct node{ int u,v,w,nxt; }e[maxm]; struct point{ int id,cost,oil; bool operator <(const point a)const{ return a.cost<cost; } }; int dp[maxn][110],p[maxn]; int h[maxn],vis[maxn][110]; int n,m,k,st,ed,cnt,c; void add(int u,int v,int w) { e[cnt].u=u; e[cnt].v=v; e[cnt].w=w; e[cnt].nxt=h[u]; h[u]=cnt++; } void bfs() { memset(dp,0x3f,sizeof(dp)); memset(vis,0,sizeof(vis)); priority_queue<point> q; q.push(point{st,0,0}); dp[st][0]=0; while(!q.empty()) { point t=q.top();q.pop(); int u=t.id,cost=t.cost,o=t.oil; vis[u][o]=1; if(u==ed) { printf("%d\n",cost); return ; } if(o+1<=c&&!vis[u][o+1]&&dp[u][o]+p[u]<dp[u][o+1])//加油 { dp[u][o+1]=dp[u][o]+p[u]; q.push(point{u,dp[u][o+1],o+1}); } for(int i=h[u];i!=-1;i=e[i].nxt)//过路 { int v=e[i].v; int w=e[i].w; if(o>=w&&!vis[v][o-w]&&dp[v][o-w]>cost) { dp[v][o-w]=cost; q.push(point{v,cost,o-w}); } } } printf("impossible\n"); } int main() { int u,v,w; cnt=0; memset(h,-1,sizeof(h)); scanf("%d%d",&n,&m); for(int i=0;i<n;i++) scanf("%d",&p[i]); for(int i=0;i<m;i++) { scanf("%d%d%d",&u,&v,&w); add(u,v,w); add(v,u,w); } scanf("%d",&k); while(k--) { scanf("%d%d%d",&c,&st,&ed); bfs(); } return 0; }