POJ3411--Paid Roads

nつの都市があって、mの道、1つの道は5つの情报があって、都市aを出発して、都市bに达して、もし前に都市cに着いたことがあるならば、それではこの道の费用はpで、さもなくば费用はrです.都市1から都市nまでの最小費用を求めます.
 
分析:直接暴力で深く捜査する.もちろん、枝を少し持ってきてください.まず、実行可能な枝切りは、1つのパスがm本の図では、各ノードの到達回数の上限がm/2であり、そうでなければ1つのループに入る(m=1の場合を除く).次に最適化枝切りであり、現在の総費用が算出された最小費用よりも大きい場合はカットしてもよい.
コード:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

struct Road {
    int a, b, c, p, r;
}road[15];

int n, m;
int vis[15];
int ans;

void dfs(int x, int tot) {
    if(tot >= ans) return;
    if(x == n) {
        ans = tot;
        return;
    }
    for(int i = 0; i < m; i++) {
        int b = road[i].b;
        if(road[i].a == x && vis[b] <= 4) {
            vis[b]++;
            if(vis[road[i].c])
                dfs(b, tot+road[i].p);
            else dfs(b, tot+road[i].r);
            vis[b]--;
        }
    }
}

int main() {
    while(~scanf("%d%d", &n, &m)) {
        for(int i = 0; i < m; i++)
            scanf("%d%d%d%d%d", &road[i].a, &road[i].b, &road[i].c, &road[i].p, &road[i].r);
        ans = 1<<30;
        memset(vis, 0, sizeof(vis));
        vis[1] = 1;
        dfs(1, 0);
        if(ans == 1<<30) printf("impossible
");
        else printf("%d
", ans);
    }
    return 0;
}