题意:给出一张图,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分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ3414-Pots 解题报告+AC代码
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ2009年最新版,相当详细.................
北大POJ1004-Financial Management 解题报告+AC代码
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
poj 百练 题目分类 poj 百练 题目分类
POJ1083的代码,POJ1083的代码,POJ1083的代码
POJ1048,加强版的约瑟夫问题 难度中等
北大POJ2002-Squares 解题报告+AC代码
poj 1001答案
poj 2744子串 答案 所用的是最简单的C语言