维护优先队列的BFS
设dp[i][j]表示到达点i同时还剩j单位油时的最小花费
由于不好确定每次在某个地方要加多少油，所以每次更新队列时，加1单位油
对于每个节点，有两种选择，1，加一单位油，2，走到下一个城市
一开始没有加dp[i][j]的优化，直接往优先队列中加节点，导致队列占用太多的内存MLE了
还有注意是双向边！！！
代码：
#include<iostream> #include<queue> using namespace std; const int MAX=1005; const int inf=1<<30; struct node { int v,cost,f; bool operator < (const node &a) const { return a.cost<cost; } }; struct edge { int v,w,next; }g[MAX*100]; int dp[MAX][105],use[MAX][105],adj[MAX],p[MAX]; int n,m,e,q,cap,s,t; priority_queue<node>que; void add(int u,int v,int c) { g[e].v=v; g[e].w=c; g[e].next=adj[u]; adj[u]=e++; } int dij() { int i,u,v,w,cost,f; struct node a,b; a.v=s; a.cost=a.f=0; while(!que.empty()) que.pop(); que.push(a); while(!que.empty()) { a=que.top(); que.pop(); u=a.v; cost=a.cost; f=a.f; use[u][f]=1; if(u==t) return cost; if(f+1<=cap&&!use[u][f+1]&&dp[u][f+1]>dp[u][f]+p[u])//加一单位的油 { dp[u][f+1]=dp[u][f]+p[u]; b.v=u; b.f=f+1; b.cost=dp[u][f+1]; que.push(b); } for(i=adj[u];i!=-1;i=g[i].next) { v=g[i].v; w=g[i].w; if(f>=w&&!use[v][f-w]&&dp[v][f-w]>cost)//油足够时，开往下一站 { dp[v][f-w]=cost; b.v=v; b.f=f-w; b.cost=dp[v][f-w]; que.push(b); } } } return -1; } int main() { int i,j,w; e=0; memset(adj,-1,sizeof(adj)); scanf("%d%d",&n,&m); for(i=0;i<n;i++) scanf("%d",&p[i]); while(m--) { scanf("%d%d%d",&i,&j,&w); add(i,j,w); add(j,i,w); } scanf("%d",&q); while(q--) { scanf("%d%d%d",&cap,&s,&t); memset(use,0,sizeof(use)); for(i=0;i<n;i++) for(j=0;j<=100;j++) dp[i][j]=inf; dp[s][0]=0; i=dij(); if(i!=-1) printf("%d/n",i); else puts("impossible"); } return 0; }
