UVA 11367 Full Tank?(bfs最短路) - c++编程基础

TOP

UVA 11367 Full Tank?(bfs最短路)

2014-11-23 17:59:12 来源: 作者: 【大中小】浏览:11次

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

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

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define FF(i, a, b) for(int i=a; i=b; i--)
#define REP(i, n) for(int i=0; i rhs.cost;
    }
};
struct Edge
{
    int to, dist;
};
vector edges;
vector 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 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(rescost+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;
}


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：hdu2159 二维完全背包	下一篇：C与C++中struct的区别

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: