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;
}

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