POJ-3411 : Paid Roads
問題概要
頂点数n(<10)、辺数m(<10)の有向グラフが与えられる。各辺を利用するにはコストx[i]か、既に特定の頂点を通って入ればy[i]のコストを支払えばよい。1からnへの最短路を求める問題。
解法
既に通った頂点集合と今いる頂点を組にしてDPすればよい。ただし、適切なトポロジカル順序をつけるのが難しいのでベルマンフォードのように適当にn回回して緩和する。
acceptされたコード
#include <cstdio> #include <algorithm> using namespace std; const int INF = int(1.05e9); template<typename numType> inline bool updateMin(numType& old, const numType& test) { if (old > test) { old = test; return true; } return false; } const int MAX_N = 10; const int MAX_M = 10; int N, M; int as[MAX_M], bs[MAX_M], cs[MAX_M], ps[MAX_M], rs[MAX_M]; int opt[1<<MAX_N][MAX_N]; void init() { scanf("%d%d", &N, &M); for (int i = 0; i < M; ++i) { scanf("%d%d%d%d%d", as+i, bs+i, cs+i, ps+i, rs+i); --as[i]; --bs[i]; --cs[i]; } } void solve() { for (int i = 0; i < 1<<N; ++i) { fill(opt[i], opt[i] + N, INF); } int ans = INF; opt[1<<0][0] = 0; for (int bit = 0; bit < 1<<N; ++bit) { for (int _ = 0; _ < N; ++_) { for (int i = 0; i < N; ++i) { for (int j = 0; j < M; ++j) { if (as[j] == i) { updateMin(opt[bit|(1<<bs[j])][bs[j]], opt[bit][i] + min(rs[j], ((bit>>cs[j])&1) ? ps[j] : INF)); } } } } } for (int bit = 0; bit < 1<<N; ++bit) { updateMin(ans, opt[bit][N-1]); } if (ans == INF) { puts("impossible"); } else { printf("%d\n", ans); } } int main() { init(); solve(); return 0; }