本文主要是介绍POJ 3635 Full Tank? 最短路变形，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：给出一张图，n<=1000,m<=10000. 有一辆车想从图的一个地方到达另外一个地方，每个点是一个卖油的地方，每个地方买的有价格不一样，车的最大装油量是c，求初始点到终止点的最小花费。
网上大部分的思路都是类似于dij的那种扩展。
首先定义一个二维数组dp。 dp[i][j] 表示走到i点剩余j个单位的汽油时的最小花费
然后维护一个优先队列。 每次有两种可扩展的状态，一是加一个单位的油，二是走向邻接点，然后不断的将状态加入优先队列中
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#define MAXN 1005
#define MAXM 100005
#define INF 1000000000
using namespace std;
struct Edge
{int v, w, next;
}edge[MAXM];
struct Node
{int v, cost, f;bool operator <(const Node &a) const{return a.cost < cost;}
};
int head[MAXN], e, n, m, cap;
int dp[MAXN][105], used[MAXN][105], p[MAXN];
int s, t, ask;
priority_queue<Node>q;
void init()
{memset(head, -1, sizeof(head));e = 0;
}
void ready()
{for(int i = 0; i < n; i++)for(int j = 0; j <= 100; j++)dp[i][j] = INF;dp[s][0] = 0;memset(used, 0, sizeof(used));while(!q.empty()) q.pop();
}
void insert(int x, int y, int w)
{edge[e].v = y;edge[e].w = w;edge[e].next = head[x];head[x] = e++;
}
int bfs()
{Node a, b;a.v = s, a.cost = 0, a.f = 0;q.push(a);while(!q.empty()){a = q.top();q.pop();int u = a.v;int cost = a.cost;int f = a.f;used[u][f] = 1;if(u == t) return cost;if(f + 1 <= cap && !used[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];q.push(b);}for(int i = head[u]; i != -1; i = edge[i].next){int v = edge[i].v;int w = edge[i].w;if(f >= w && !used[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];q.push(b);}}}return -1;
}
int main()
{int x, y, w;scanf("%d%d", &n, &m);init();for(int i = 0; i < n; i++) scanf("%d", &p[i]);while(m--){scanf("%d%d%d", &x, &y, &w);insert(x, y, w);insert(y, x, w);}scanf("%d", &ask);while(ask--){scanf("%d%d%d", &cap, &s, &t);ready();int ans = bfs();if(ans != -1) printf("%d\n", ans);else printf("impossible\n");}return 0;
}
这篇关于POJ 3635 Full Tank? 最短路变形的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
