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ほんとに問題文読めない…