大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。
做题情绪:先前看过一次,感觉做多了状态压缩之后。再做这题就非常顺手了。
解题思路: BFS + 状态压缩
一个城市能够走多次,so ~ > 须要用状态压缩。開始用了优先队列可是后来发现不能够用。当中例子用优先队列就过不了,于是把标记数组改为记录达到某个城市达到某种 状态的最小花费,假设搜到某个状态花费比当前状态小。更新标记数组的花费。就继续搜下去。否则不向下搜,这样搜出全部的情况就能够了。
(注意推断的时候要推断终点城市是否在状态里,開始有点脑残了推断是否全部城市都到达了)。
代码:
#include<iostream> #include<sstream> #include<map> #include<cmath> #include<fstream> #include<queue> #include<vector> #include<sstream> #include<cstring> #include<cstdio> #include<stack> #include<bitset> #include<ctime> #include<string> #include<cctype> #include<iomanip> #include<algorithm> using namespace std ; #define INT __int64 #define L(x) (x * 2) #define R(x) (x * 2 + 1) const int INF = 0x3f3f3f3f ; const double esp = 0.0000000001 ; // 问 mod HDU 5063 const double PI = acos(-1.0) ; const int mod = 1e9 + 7 ; const int MY = 10 + 5 ; const int MX = (1<<10) + 5 ; int n ,m ; int vis[MY][MX] ; struct node { int c1 ,c2 ; }mp[MY][MY][MY] ; struct NODE { int x ,cost ,key ; } ; int bfs(int x) { int ans = INF ; queue<NODE> q ; NODE curt ,next ; curt.x = x ; // 终于到达的点 curt.cost = 0 ; // 花费 curt.key = 1 ; // 状态 vis[0][1] = 0 ; q.push(curt) ; while(!q.empty()) { curt = q.front() ; q.pop() ; if(curt.key &(1<<(n-1))) ans = min(ans ,curt.cost) ; for(int i = 0 ;i < n ; ++i) for(int j = 0 ;j < n ; ++j) if(mp[curt.x][i][j].c1 != -1) { int costA = INF ,costB = INF ; next.key = curt.key ; if(next.key&(1<<j)) // 预支点在里面 costA = curt.cost + mp[curt.x][i][j].c1 ; // 原先的花费加上当前花费 costB = curt.cost + mp[curt.x][i][j].c2 ; next.cost = min(costA ,costB) ; next.x = i ; if(!(next.key&(1<<i))) next.key |= (1<<i) ; if(vis[i][next.key] > next.cost) { vis[i][next.key] = next.cost ; q.push(next) ; } } } return ans ; } int main() { //freopen("input.txt" ,"r" ,stdin) ; int u ,v ,t ,c1 ,c2 ; while(~scanf("%d%d" ,&n ,&m)) { memset(mp ,-1 ,sizeof(mp)) ; for(int S = 0 ;S < (1<<n) ; ++S) for(int i = 0 ;i < n ; ++i) vis[i][S] = INF ; for(int i = 0 ;i < m ; ++i) { scanf("%d%d%d%d%d" ,&u ,&v ,&t ,&c1 ,&c2) ; u-- ; v-- ; t-- ; if(mp[u][v][t].c1 != -1) // 防止重边(本题不知是否存在) mp[u][v][t].c1 = min(mp[u][v][t].c1 ,c1) ; else mp[u][v][t].c1 = c1 ; if(mp[u][v][t].c2 != -1) mp[u][v][t].c2 = min(mp[u][v][t].c2 ,c2) ; else mp[u][v][t].c2 = c2 ; } int mx = bfs(0) ; if(mx != INF) cout<<mx<<endl ; else cout<<"impossible"<<endl ; } return 0 ; }
版权声明:本文博客原创文章。博客,未经同意,不得转载。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117176.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...