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