POJ 3411 Paid Roads

引き続き蟻本の練習問題から。
3411 -- Paid Roads

問題概要

　有向グラフが与えられる。コストは少し特殊で、辺ごとに特定の頂点cが決まっておりcをすでに通過していたらp,そうでなかったらqになる（これは書いてないけどp<=qなのでp, qが両方選べたらpを選ぶべき）。
　１からNへの最短コストを求めろ、という問題。

解法

　戻ってくるパターンがあるので普通にビットDPするのだと解けない。ダイクストラ法。

#include <utility>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <queue>
using namespace std;
#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);++i)
#define rep(i,n) REP(i, 0, n)

struct Edge {
    int to, c, p, r;
    Edge(int t, int c, int p, int r)
         : to(t), c(c), p(p), r(r) {}
    // p <= r
};

const int INF = 1e9;
int dp[1 << 10][10];
typedef pair<int, pair<int, int> > state;
int main() {
    int N, M;
    scanf("%d%d", &N, &M);
    vector<vector<Edge> > adj(N);
    rep(_, M) {
        int from, to, c, p, r;
        scanf("%d%d%d%d%d", &from, &to, &c, &p, &r);
        --from;
        --to;
        --c;
        adj[from].push_back(Edge(to, c, p, r));
    }
    int start = 0, goal = N - 1;
    rep(i, 1 << 10) fill_n(dp[i], 10, INF);
    dp[1 << start][start] = 0;
    priority_queue<state, vector<state>, greater<state> >que;
    que.push(state(0, make_pair(1 << start, start)));
    while(!que.empty()) {
        int cos = que.top().first, S = que.top().second.first, cur = que.top().second.second;
        que.pop();
        if(dp[S][cur] < cos) continue;
        rep(i, adj[cur].size()) {
            Edge e = adj[cur][i];
            int cost = (S & (1 << e.c)) ? e.p : e.r;
            if(dp[S | (1 << e.to)][e.to] > dp[S][cur] + cost) {
                dp[S | (1 << e.to)][e.to] = dp[S][cur] + cost;
                que.push(state(dp[S | (1 << e.to)][e.to], make_pair(S | (1 << e.to), e.to)));
            }
        }
    }
    int ans = INF;
    rep(S, 1 << N)
      ans = min(ans, dp[S][goal]);
    if(ans == INF)
      puts("impossible");
    else
      printf("%d\n", ans);
    return 0;
}