POJ 3411: Paid Roads

http://poj.org/problem?id=3411

問題文をよく読みましょう。(a,b)は有向辺です。無向辺でやったあとを残しておきました。
ベルマンフォードっぽくbitDPをやればよい。

int N, M;
int A[20], B[20], C[20], P[20], R[20];
int dp[1 << 11][11];

int main() {
	scanf("%d%d", &N, &M);
	rep(i, 0, M) {
		scanf("%d%d%d%d%d", &A[i], &B[i], &C[i], &P[i], &R[i]);
		A[i]--; B[i]--; C[i]--;
	}
	rep(bit, 0, (1 << N))
		rep(i, 0, N) dp[bit][i] = inf;

	dp[1][0] = 0;

	rep(k, 0, 3 * N) {
		rep(bit, 1, (1 << N)) {
			rep(i, 0, N) {
				if(!(bit & (1 << i)) || dp[bit][i] >= inf) continue;

				rep(j, 0, M) {
					int a = A[j], b = B[j], c = C[j];
					if(i == a) {
						int mask = bit;
						if(!(mask & (1 << b))) mask |= (1 << b);
						MIN(dp[mask][b], dp[bit][i] + ((bit & (1 << c)) ? P[j] : R[j]));
					}
					/*
					else if(i == b) {
						int mask = bit;
						if(!(mask & (1 << a))) mask |= (1 << a);
						else MIN(dp[mask][a], dp[bit][i] + ((bit & (1 << c)) ? P[j] : R[j]));
					}
					*/
				}
			}
		}
	}
	int res = inf;
	rep(bit, 0, (1 << N)) MIN(res, dp[bit][N - 1]);
	if(res == inf) printf("impossible\n");
	else printf("%d\n", res);

	return 0;
}

POJほんとに問題文読めない…