问题描述

有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第一次被取出为止。

代码

#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);
    }
}

发表评论

邮箱地址不会被公开。 必填项已用*标注