本文主要是介绍poj3411--Paid Roads(bfs+状压)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：点击打开链接
题目大意：有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") ;elseprintf("%d\n", min1) ;}return 0 ;
}这篇关于poj3411--Paid Roads(bfs+状压)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
