题目大概说,一辆带有一个容量有限的油箱的车子在一张图上行驶,每行驶一单位长度消耗一单位油,图上的每个点都可以加油,不过都有各自的单位费用,问从起点驾驶到终点的最少花费是多少?
这题自然想到图上DP,通过最短路来转移方程:
- dp[u][c]表示当前在u点油箱还有c单位油时的最少花费
不过,我T得好惨,因为在转移时我通过枚举在各个结点加多少油转移,这样对于每个状态都for一遍枚举,整个时间复杂度还得乘上转移的代价,即油箱最大容量。。。
事实上,状态dp[u][c]只需要向两个方向转移:
- 向dp[u][c+1]转移,即原地加一单位油
- 向dp[v][c-w(u,v)]((u,v)∈E 且 w(u,v)<=c),即走到下一个结点
另外用SPFA会TLE,用Dijkstra即可,1000×100的状态数稳定AC。
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
#define INF (1<<30)
#define MAXN 1111
#define MAXM 111111 struct Edge{
int v,w,next;
}edge[MAXM<<];
int NE,head[MAXN];
void addEdge(int u,int v,int w){
edge[NE].v=v; edge[NE].w=w; edge[NE].next=head[u];
head[u]=NE++;
} int vs,vt,cap;
int price[MAXN],d[MAXN][];
bool vis[MAXN][]; struct Node{
int u,w,d;
Node(int _u=,int _w=,int _d=):u(_u),w(_w),d(_d){}
bool operator<(const Node &nd)const{
return nd.d<d;
}
}; int dijkstra(){
memset(d,,sizeof(d));
memset(vis,,sizeof(vis));
priority_queue<Node> que;
for(int i=; i<=cap; ++i){
d[vs][i]=price[vs]*i;
que.push(Node(vs,i,d[vs][i]));
}
while(!que.empty()){
Node nd=que.top(); que.pop();
if(nd.u==vt) return nd.d;
if(vis[nd.u][nd.w]) continue;
vis[nd.u][nd.w]=;
if(nd.w<cap && d[nd.u][nd.w+]>d[nd.u][nd.w]+price[nd.u]){
d[nd.u][nd.w+]=d[nd.u][nd.w]+price[nd.u];
que.push(Node(nd.u,nd.w+,d[nd.u][nd.w+]));
}
for(int i=head[nd.u]; i!=-; i=edge[i].next){
int v=edge[i].v;
if(edge[i].w>nd.w) continue;
int nw=nd.w-edge[i].w;
if(d[v][nw]>d[nd.u][nd.w]){
d[v][nw]=d[nd.u][nd.w];
que.push(Node(v,nw,d[v][nw]));
}
}
}
return INF;
} int main(){
int n,m,q,a,b,c;
scanf("%d%d",&n,&m);
for(int i=; i<n; ++i){
scanf("%d",price+i);
}
memset(head,-,sizeof(head));
while(m--){
scanf("%d%d%d",&a,&b,&c);
addEdge(a,b,c);
addEdge(b,a,c);
}
scanf("%d",&q);
while(q--){
scanf("%d%d%d",&cap,&vs,&vt);
int res=dijkstra();
if(res==INF) puts("impossible");
else printf("%d\n",res);
}
return ;
}