`

POJ 3635 Full Tank? (最短路变形 + BFS)

c 
阅读更多

 

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 ≤ pi ≤ 100, where pi is the fuel price in the ith city. Then follow m lines with three integers 0 ≤ uv < 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

 

 

题意:给出一张图,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;
}

 

分享到:
评论

相关推荐

    POJ3026-Borg Maze【BFS+Prim】

    《POJ3026-Borg Maze:BFS与Prim算法的应用解析》 在计算机科学领域,图论是解决问题的重要工具之一,而BFS(广度优先搜索)和Prim算法则是其中的两种经典算法。本篇文章将围绕北大POJ3026题目“Borg Maze”来探讨...

    POJ1426-Find The Multiple【BFS+同余模】

    【标题】"POJ1426-Find The Multiple【BFS+同余模】"是一道来源于北京大学在线编程平台POJ的算法题目,主要涉及到了广度优先搜索(BFS)与同余模运算的知识点。这道题目要求解决的是寻找一个整数的倍数问题,可能...

    POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】

    《POJ3009-Curling 2.0:深度优先搜索、向量、回溯与剪枝的综合应用》 北京大学在线编程平台上的POJ3009题目名为"Curling 2.0",它是一道涉及到算法与数据结构的复杂问题,主要考察了参赛者对深度优先搜索(DFS)、...

    acm 题目汇总(好东西)

    POJ 3463 "Sightseeing" 和 POJ 3635 "full tank?" 是较复杂的最短路问题,可能需要更深入理解Dijkstra算法或者结合其他策略,如参数搜索。 生成树问题涉及找到一个无环加权图的子集,使得这个子集形成的树连接所有...

    POJ3733-Changing Digits【DFS+强剪枝】

    【标题】"POJ3733-Changing Digits【DFS+强剪枝】"是一个来自北京大学在线评测系统POJ的编程题目,该题目主要涉及深度优先搜索(DFS)算法和强剪枝策略。在算法竞赛和编程挑战中,这类问题通常要求参赛者通过编写...

    北大POJ初级-所有题目AC代码+解题报告

    【标题】"北大POJ初级-所有题目AC代码+解题报告" 涉及的知识点主要集中在编程、算法和在线判题系统方面。北京大学(Peking University, 简称PKU)的POJ(Peking University Online Judge)是一个为计算机科学爱好者...

    POJ2186-Popular Cows【Tarjan+极大强连通分量+缩点】

    POJ2186-Popular Cows 【Tarjan+极大强连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573

    POJ3373-Changing Digits【DFS+强剪枝】

    标题“POJ3373-Changing Digits【DFS+强剪枝】”涉及的是一个编程竞赛中的问题,这个问题在北大POJ(北京大学在线评测系统)平台上被提出。"Changing Digits"是一个算法挑战,而解决方案是通过深度优先搜索(DFS)...

    POJ_3131.zip_POJ 八数码_poj

    标题中的“POJ_3131.zip_POJ 八数码_poj”指的是一个与编程竞赛网站POJ(Problem Set Algorithm)相关的项目,具体是针对3131号问题的解决方案,该问题涉及到了八数码游戏。八数码游戏,又称滑动拼图,是一个经典的...

    POJ1753-Flip Game

    两个解决方案的代码文件“POJ1753-Flip Game(BFS+bit).cpp”和“POJ1753-Flip Game(DFS+enum).cpp”分别实现了BFS和DFS策略。阅读这些代码可以帮助理解如何将理论转换为实际的程序实现。 五、文档说明 “POJ1753-...

    POJ3414-Pots

    标题“POJ3414-Pots”是一个编程竞赛题目,源自北京大学的在线判题系统POJ(Problem Online Judge)。这个题目主要考察的是算法设计和实现能力,通常涉及计算机科学中的数据结构和算法知识。 解题报告是参赛者在...

    NOI2002.rar_NOI 2002 dragon_poj bfs

    标题中的“NOI2002.rar_NOI 2002 dragon_poj bfs”提到了几个关键元素:NOI(全国青少年信息学奥林匹克),2002年赛事,dragon问题,以及poj_bfs。这表明我们即将讨论的是2002年全国青少年信息学奥林匹克竞赛中的...

    POJ动态规划题目全面总结

    PKU Online Judge上面很全面的...动态规划是ACM考点中最重要的一大类算法之一,对于工作人员来说,动态规划也是实际开发中经常会遇到的算法。这是POJ上面很多DP题目的总结与深刻分析。利于算法学习,学长给的,在此分享

    poj 图论 集合

    POJ3635 - Full Tank? - **题目链接**:[POJ3635](http://acm.pku.edu.cn/JudgeOnline/problem?id=3635) - **解法概述**:这是一道关于油量消耗的问题,需要考虑到每个节点到终点的距离以及油箱的容量等因素。 - ...

    西北工业大学POJ试题C++答案代码+课程设计

    "西北工业大学POJ试题C++答案代码+课程设计"这一标题表明了资源的主要内容,涉及两个核心部分:一是西北工业大学的编程竞赛(POJ,Problem Oriented Judge System)的C++解题代码,二是与这些题目相关的课程设计。...

    POJ1018-Communication System

    北大POJ1018-Communication System 解题报告+AC代码

    poj各种分类

    标题和描述中的“poj各种分类”主要指向的是在POJ(Peking University Online Judge)平台上,根据解题策略和算法类型对题目进行的分类。POJ作为一个知名的在线编程平台,提供了大量的算法练习题,适合从初学者到...

    POJ算法题目分类

    * 图的深度优先遍历和广度优先遍历:图的深度优先遍历和广度优先遍历是指遍历图的两种方式,如 poj1860、poj3259、poj1062、poj2253、poj1125、poj2240。 * 最短路径算法:最短路径算法是指计算图中两点之间的最短...

Global site tag (gtag.js) - Google Analytics