题目链接：点击打开链接
题目大意：有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 0x3f3f3f3fstruct 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") ;elseprintf("%d\n", min1) ;}return 0 ;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
，无神的瞳孔，我迫切想逃离这周遭被钢筋混凝土堆架的城市，
