题目链接：

id=3411">点击打开链接

题目大意：有n个点。m条有向边，经过边须要一个花费，a b c p q代表 a到b的一条道路，假设经过这条边之前经过c点，那么须要p的花费，否则须要q的花费。问从1点到n点的最小花费。

方法1、每条边可能会经过多次，每一个点也能够经过多次，这样就没有了边界不能直接进行dfs，由于要记录之前经过的边。所以使用状压，dis[i][j]：当前在第i个点。j表示经过了的点，这样就能够得到推导的公式，按spfa的方式。跑出最短路

方法2、最多仅仅有10个点，那么假设1个点被反复经过3次以上，那么再经过它就仅仅会添加最小值，不会优化结果，也就是一个闸值，所以控制訪问点的次数。直接dfs+剪枝就能求解

#include <cstdio>

#include <cstring>

#include <queue>

#include <algorithm>

using namespace std ;

#define INF 0x3f3f3f3f

struct nn{

    int a , b , c , p , q ;

    int next ;

}edge[20];

int head[20] ,cnt ;

int n , m , min1 ;

struct node{

    int a , k ;

    int w ;

} node_p , node_q ;

queue <node> que ;

int vis[12][1100] , dis[12][1100] ;

void add(int a,int b) {

    edge[cnt].a = a ; edge[cnt].b = b ;

    scanf("%d %d %d", &edge[cnt].c, &edge[cnt].p, &edge[cnt].q) ;

    edge[cnt].next = head[a] ; head[a] = cnt++ ;

}

int main() {

    int i , a , b , c ;

    while( scanf("%d %d", &n, &m) != EOF ) {

        memset(head,-1,sizeof(head)) ;

        memset(vis,0,sizeof(vis)) ;

        memset(dis,INF,sizeof(dis)) ;

        cnt = 0 ;

        while( m-- ) {

            scanf("%d %d", &a, &b) ;

            add(a,b) ;

        }

        while( !que.empty() ) que.pop() ;

        vis[1][1] = 1 ;

        dis[1][1] = 0 ;

        node_p.a = 1 ; node_p.k = 1 ;

        node_p.w = 0 ;

        que.push(node_p) ;

        while( !que.empty() ) {

            node_p = que.front() ;

            que.pop() ;

            //printf("bbiu--> %d %d\n", node_p.a, node_p.k) ;

            vis[ node_p.a ][ node_p.k ] = 0 ;

            for(i = head[ node_p.a ] ; i != -1 ; i = edge[i].next) {

                b = edge[i].b ;

                c = 1<<(edge[i].c-1) ;

                if( node_p.k & c ){

                    if( dis[ node_p.a ][ node_p.k ] + edge[i].p < dis[ edge[i].b ][ node_p.k ] ) {

                        dis[ edge[i].b ][ node_p.k ] = dis[ node_p.a ][ node_p.k ] + edge[i].p ;

                        if( !vis[ edge[i].b ][ node_p.k ] ) {

                            vis[ edge[i].b ][ node_p.k ] = 1 ;

                            node_q.a = edge[i].b ;

                            node_q.k = node_p.k ;

                            node_q.w = dis[ edge[i].b ][ node_p.k ] ;

                            que.push(node_q) ;

                        }

                    }

                }

                else {

                    if( dis[ node_p.a ][ node_p.k ] + edge[i].q < dis[ edge[i].b ][ node_p.k|c ] ) {

                        dis[ edge[i].b ][ node_p.k|c ] = dis[ node_p.a ][ node_p.k ] + edge[i].q ;

                        if( !vis[ edge[i].b ][ node_p.k|c ] ) {

                            vis[ edge[i].b ][ node_p.k|c ] = 1 ;

                            node_q.a = edge[i].b ;

                            node_q.k = node_p.k|c ;

                            node_q.w = dis[ edge[i].b ][ node_p.k|c ] ;

                            que.push(node_q) ;

                        }

                    }

                }

            }

        }

        min1 = INF ;

        for(i = 0 ; i < (1<<n) ; i++){

            min1 = min(min1,dis[n][i]) ;

            //printf("n - i == %d , %d \n", i, dis[n][i]) ;

        }

        if( min1 == INF )

            printf("impossible\n") ;

        else

            printf("%d\n", min1) ;

    }

    return 0 ;

}