POJ 3635 Full Tank? （最短路变形 + BFS）

 

Full Tank?

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 5673		Accepted: 1853

Description

After going through the receipts from your car trip through Europe this summer, you realised that the gas prices varied between the cities you visited. Maybe you could have saved some money if you were a bit more clever about where you filled your fuel?

To help other tourists (and save money yourself next time), you want to write a program for finding the cheapest way to travel between cities, filling your tank on the way. We assume that all cars use one unit of fuel per unit of distance, and start with an empty gas tank.

Input

The first line of input gives 1 ≤ n ≤ 1000 and 0 ≤ m ≤ 10000, the number of cities and roads. Then follows a line with n integers 1 ≤ p_i ≤ 100, where p_i is the fuel price in the ith city. Then follow m lines with three integers 0 ≤ u, v < n and 1 ≤ d ≤ 100, telling that there is a road between u and v with length d. Then comes a line with the number 1 ≤ q ≤ 100, giving the number of queries, and q lines with three integers 1 ≤ c ≤ 100, s and e, where c is the fuel capacity of the vehicle, s is the starting city, and e is the goal.

Output

For each query, output the price of the cheapest trip from s to e using a car with the given capacity, or "impossible" if there is no way of getting from s to e with the given car.

Sample Input

5 5
10 10 20 12 13
0 1 9
0 2 8
1 2 1
1 3 11
2 3 7
2
10 0 3
20 1 4

Sample Output

170
impossible

Source

Nordic 2007

 

 

题意：给出一张图，n<=1000,m<=10000.  有一辆车想从图的一个地方到达另外一个地方，每个点是一个卖油的地方，每个地方买的有价格不一样，车的最大装油量是c，求初始点到终止点的最小花费。

 

网上大部分的思路都是类似于dij的那种扩展。

首先定义一个二维数组dp。 dp[i][j] 表示走到i点剩余j个单位的汽油时的最小花费

然后维护一个优先队列。  每次有两种可扩展的状态，一是加一个单位的油，二是走向邻接点，然后不断的将状态加入优先队列中

 

【题意】
给你 n 个点，m 条边，每走 1 单位的路径都会花费 1 单位的 fuel ，并且不同的点灌油的油的价格是不同的，现在给你一些询问，每一个询问给你起点、终点以及油箱的容量，问你所需要的最少的花费可以从起点到达终点。

 

涉及两个维的图最短路，一个是费用，一个是地点。（比如在位置0有1升油是一个点,在位置0有2升油又是另外一个点)

如果把这个点抽象出来，把费用看过边，那么最少费用就可以类似dijsktra算法那样不断的加入点。

于是得到一个扩展结点的策略:

1.每一次加一升油（因为题目的条件这些都是整数，所以可以类似离散化处理,一点一点加入油)

2.如果加的油足够走到下一个结点,那就走到下一个结点吧(记得减去路上消耗的油,还有花费不变…)

(至于在第二次扩展时要不要加油,这个就不需要了.因为在第一种情况扩展结点的时候加油了…)

这里的BFS是把所有可扩展的节点都加入优先队列中，而Dijkstra是每次松弛了的点才加入，中间少了很多状态。但是思想都是一样的。不知道这题能不能像Dij那样做。

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>

using namespace std;

const int VM=1010;
const int EM=10010;
const int INF=0x3f3f3f3f;

struct Edge{
    int to,nxt;
    int cap;
}edge[EM<<1];

struct Status{
    int u,fuel,cost;
    bool operator < (const Status &a) const{
        return a.cost<cost;
    }
};

int n,m,cnt,head[VM],price[VM];
priority_queue<Status> q;
int vis[VM][110];

void addedge(int cu,int cv,int cw){
    edge[cnt].to=cv;    edge[cnt].cap=cw;   edge[cnt].nxt=head[cu];
    head[cu]=cnt++;
    edge[cnt].to=cu;    edge[cnt].cap=cw;   edge[cnt].nxt=head[cv];
    head[cv]=cnt++;
}

void push_q(int u,int f,int c){
    Status cur;
    cur.u=u;    cur.fuel=f;     cur.cost=c;
    q.push(cur);
}

int BFS(int c,int s,int e){
    memset(vis,0,sizeof(vis));
    while(!q.empty())
        q.pop();
    push_q(s,0,0);
    Status cur;
    while(!q.empty()){
        cur=q.top();
        q.pop();
        int u=cur.u,    fuel=cur.fuel,  cost=cur.cost;
        vis[u][fuel]=1;
        if(u==e)
            return cost;                        //每次有两种可扩展的状态,如下：
        if(fuel<c && !vis[u][fuel+1])           //一是加一个单位的油
            push_q(u,fuel+1,cost+price[u]);
        for(int i=head[u];i!=-1;i=edge[i].nxt)  //二是走向邻接点，然后不断的将状态加入优先队列中
            if(fuel>=edge[i].cap && !vis[edge[i].to][fuel-edge[i].cap])
                push_q(edge[i].to,fuel-edge[i].cap,cost);
    }
    return -1;
}

int main(){

    //freopen("input.txt","r",stdin);

    while(~scanf("%d%d",&n,&m)){
        cnt=0;
        memset(head,-1,sizeof(head));
        for(int i=0;i<n;i++)
            scanf("%d",&price[i]);
        int u,v,w;
        while(m--){
            scanf("%d%d%d",&u,&v,&w);
            addedge(u,v,w);
        }
        int q,c,s,e;
        scanf("%d",&q);
        while(q--){
            scanf("%d%d%d",&c,&s,&e);
            int ans=BFS(c,s,e);
            if(ans==-1)
                printf("impossible\n");
            else
                printf("%d\n",ans);
        }
    }
    return 0;
}