首页 > 搜索 > BFS搜索 > HDU 1676 Full Tank?-BFS-[解题报告] C++
2013
12-21

HDU 1676 Full Tank?-BFS-[解题报告] C++

Full Tank?

问题描述 :

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.

输入:

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 <= 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.

输出:

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.

样例输入:

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

样例输出:

170
impossible

n个点m条无向边的图,油箱有上限,每个单位的汽油能走1单位距离,每个城市的油价val[i], 对于每个query,求s到e的最小花费。

dp[i][j]表示到达第i个城市,油箱剩余油量j时的最小花费。用bfs扩充节点,每个点拆成100个节点,时间复杂度还是可以接受的。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<fstream>
#include<sstream>
#include<bitset>
#include<vector>
#include<string>
#include<cstdio>
#include<cmath>
#include<stack>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define FF(i, a, b) for(int i=a; i<b; i++)
#define FD(i, a, b) for(int i=a; i>=b; i--)
#define REP(i, n) for(int i=0; i<n; i++)
#define CLR(a, b) memset(a, b, sizeof(a))
#define debug puts("**debug**")
#define LL long long
#define PB push_back
using namespace std;

const int maxn = 1010;
int n, m, val[maxn], dp[maxn][101];
int Q, C, S, E;
struct Node
{
    int u, cost, res;//当前节点,花费,剩余油量
    bool operator < (const Node rhs) const
    {
        return cost > rhs.cost;
    }
};
struct Edge
{
    int to, dist;
};
vector<Edge> edges;
vector<int> G[maxn];

inline void init()
{
    REP(i, n) G[i].clear(); edges.clear();
}

void add(int a, int b, int c)
{
    edges.PB((Edge){b, c});
    edges.PB((Edge){a, c});
    int nc = edges.size();
    G[a].PB(nc-2); G[b].PB(nc-1);
}

void bfs()
{
    REP(i, n) REP(j, C+1) dp[i][j] = 0;
    priority_queue<Node> q; q.push((Node){S, 0, 0});
    while(!q.empty())
    {
        Node x = q.top(); q.pop();
        int u = x.u, cost = x.cost, res = x.res, nc = G[x.u].size();
        if(u == E)
        {
            printf("%d\n", cost);
            return ;
        }
        //考虑当前状态,再多加一点油是否会是更优解
        if(res<C && (dp[u][res+1]==0 || dp[u][res+1]>cost+val[u]))
            dp[u][res+1] = cost+val[u],q.push((Node){u,dp[u][res+1],res+1});

        REP(i, nc)
        {
            int v = edges[G[u][i]].to, dist = edges[G[u][i]].dist;
            if(res < dist) continue; //如果油量不够走到下一个节点就continue
            //如果靠当前油量走到下一个节点会是更优解
            if(dp[v][res-dist] == 0 || dp[v][res-dist] > cost)
                dp[v][res-dist] = cost, q.push((Node){v, cost, res-dist});
        }
    }
    puts("impossible");
    return ;
}

int main()
{
    while(~scanf("%d%d", &n, &m))
    {
        init();
        REP(i, n) scanf("%d", &val[i]);
        int a, b, c;
        REP(i, m)
        {
            scanf("%d%d%d", &a, &b, &c);
            add(a, b, c);
        }
        scanf("%d", &Q);
        while(Q--)
        {
            scanf("%d%d%d", &C, &S, &E);
            bfs();
        }
    }
    return 0;
}

解题报告转自:http://blog.csdn.net/diary_yang/article/details/9982267


  1. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法

  2. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), [email protected]
    * Organization: AMS/ICT
    *
    * =====================================================================================
    */

    #include
    #include

    using namespace std;

    int main()
    {
    stack st;
    int n,i,j;
    int test;
    int a[100001];
    int b[100001];
    while(cin>>n)
    {
    for(i=1;i>a[i];
    for(i=1;i>b[i];
    //st.clear();
    while(!st.empty())
    st.pop();
    i = 1;
    j = 1;

    while(in)
    break;
    }
    while(!st.empty()&&st.top()==b[j])
    {
    st.pop();
    j++;
    }
    }
    if(st.empty())
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    }
    return 0;
    }