Dylan's Blog
0%

POJ3635 Full Tank? [堆+搜索]

Posted on Edited on In

问题描述

有N(1<=N<=1000)个城市和M(1<=M<=10000)条道路，构成一张无向图。在每个城市里面都有一个加油站，不同的加油站的价格不一样。通过每一条道路的油耗就是该道路的边权。你需要回答q(q<=100)个问题,在每个问题中，请计算出油箱容量为C(1<=C<=100)的车子，从起点S开到终点T至少要话多少油钱？

输入

第一行两个数字n,m。 接下来一行n个数字描述每个城市的油价。 接下来m行描述每行描述一条道路。 接下来一行一个数字q。 然后q行描述q个问题。

输出

一共q行，每行输出每个问题的油钱。如果不能到达，输出impossible。

思路

这题的主要思想就是优先队列搜索。我们对于每一个问题都进行一次优先队列BFS。对于每一个状态我们储存3个信息：所在城市，当前油量，当前花费。再用用一个二维数组d记录最少花费。

接下来有两中扩展方式，一是在当前城市加1L油，二是到相邻的城市并且消耗油量。我们不断从堆顶取出花费最少的状态，直到T第一次被取出为止。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#define MAXN 1005
#define MAXE 10005
using namespace std;

int n, m, u, v, dis, e, s, c, Q, cnt, head[MAXN], val[MAXN], d[MAXN][110];

struct Node
{
    int city, fuel, cost;
    Node(int x, int y, int z)
    {
        city=x; fuel=y; cost=z;
    }
    friend bool operator < (Node x, Node y)
    {
        return x.cost>y.cost;
    }
};
struct Edge {int next, to, dis;} edge[MAXE*2];

void addedge(int from, int to, int dis)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    edge[cnt].dis=dis;
    head[from]=cnt;
}

void bfs(int s, int e, int v)
{
    priority_queue<Node> q;
    memset(d, 0x3f, sizeof(d));
    d[s][0]=0;
    q.push(Node(s, 0, 0));
    while(!q.empty())
    {
        int x=q.top().city, f=q.top().fuel, c=q.top().cost;
        q.pop();
        if(x==e) {printf("%d\n", c); return;}
        if(f<v && d[x][f]+val[x]<d[x][f+1])
        {
            d[x][f+1]=d[x][f]+val[x];
            q.push(Node(x, f+1, d[x][f+1]));
        }
        for(int i=head[x]; i; i=edge[i].next)
        {
            int to=edge[i].to, dis=edge[i].dis;
            if(f>=dis && c<d[to][f-dis])
            {
                d[to][f-dis]=c;
                q.push(Node(to, f-dis, d[to][f-dis]));
            }
        }
    }
    printf("impossible\n");
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++) scanf("%d", &val[i]);
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d%d", &u, &v, &dis);
        addedge(u+1, v+1, dis);
        addedge(v+1, u+1, dis);
    }
    scanf("%d", &Q);
    for(int i=1; i<=Q; i++)
    {
        scanf("%d%d%d", &c, &s, &e);
        bfs(s+1, e+1, c);
    }
}