放牧代码和思想
专注自然语言处理、机器学习算法
    This thing called love. Know I would've. Thrown it all away. Wouldn't hesitate.

POJ 3411 Paid Roads 题解 《挑战程序设计竞赛》

目录

POJ 3411 Paid Roads

开路:N个城市间有m条单向路,分别从a到b,可以在c处交P路费,也可以直接交R路费。那么问题来了,你的挖掘机怎么开最省钱?

3.4熟练掌握动态规划

状态压缩DP

乍一看可以Dijkstra,实际上的确可以Dijkstra。不过多了一个预交费的c,所以在遍历的时候多了一维状态,这个维度储存当前走过的城市集合。在Dijkstra的时候,如果走过了c那么就有两个选择,选其中最省的即可;否则没得选。

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#define MAX_N 10 + 1

using namespace std;

class Road
{
public:
    int a, b, c, P, R;

    Road(int a, int b, int c, int P, int R) : a(a), b(b), c(c), P(P), R(R)
    {}
};

class State
{
public:
    int current,    // 当前位置
            cost,   // 总花费
            S;      // 已通过的城市

    State(int current, int cost, int S) : current(current), cost(cost), S(S)
    {}

    bool operator>(const State &other) const
    {
        return cost > other.cost;
    }
};

vector<Road> edge[MAX_N];  // 边的集合,edge[from]
bool visited[MAX_N][1 << MAX_N];

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    int N, m;
    cin >> N >> m;

    for (int i = 0; i < m; ++i)
    {
        int a, b, c, P, R;
        cin >> a >> b >> c >> P >> R;
        edge[a].push_back(Road(a, b, c, P, R));
    }

    priority_queue<State, vector<State>, greater<State> > que;
    que.push(State(1, 0, 1 << 1));  // 现在位于起点1,花费是0,已通过的城市的集合是{1}

    memset(visited, 0, sizeof(visited));

    State result(-1, -1, -1);

    while (!que.empty())
    {
        State p = que.top();
        que.pop();
        if (visited[p.current][p.S]) continue;

        visited[p.current][p.S] = true;

        if (p.current == N)
        {
            result = p;
            break;
        }

        for (vector<Road>::iterator it = edge[p.current].begin(); it != edge[p.current].end(); ++it)
        {
            Road e = *it;
            int cost = p.cost;
            if (p.S & (1 << e.c))
            {
                cost += min(e.P, e.R);
            }
            else
            {
                cost += e.R;
            }
            que.push(State(e.b, cost, p.S | (1 << e.b)));
        }
    }

    if (result.current == -1)
    {
        cout << "impossible\n";
    }
    else
    {
        cout << result.cost << endl;
    }
#ifndef ONLINE_JUDGE
    fclose(stdin);
#endif
    return 0;
}
13569812 hankcs 3411 Accepted 244K 16MS C++ 2079B 2014-10-26 22:30:13

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » POJ 3411 Paid Roads 题解 《挑战程序设计竞赛》

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的作品

HanLP自然语言处理包《自然语言处理入门》