POJ 3411 Paid Roads (状态压缩+BFS)
状态 压缩 poj BFS
2023-09-11 14:17:18 时间
题意:有n座城市和m(1<=n,m<=10)条路。现在要从城市1到城市n。有些路是要收费的,从a城市到b城市,如果之前到过c城市,那么只要付P的钱,
如果没有去过就付R的钱。求的是最少要花多少钱。
析:BFS,然后由于走的路线不同,甚至边或者点都可能多走,所以用状态压缩。然后本题有坑啊,有重连,而且有很多条重边,所以多走几次就好了。
代码如下:
#pragma comment(linker, "/STACK:1024000000,1024000000") #include <cstdio> #include <string> #include <cstdlib> #include <cmath> #include <iostream> #include <cstring> #include <set> #include <queue> #include <algorithm> #include <vector> #include <map> #include <cctype> #include <cmath> #include <stack> #include <sstream> #define debug() puts("++++"); #define gcd(a, b) __gcd(a, b) #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define freopenr freopen("in.txt", "r", stdin) #define freopenw freopen("out.txt", "w", stdout) using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> P; const int INF = 0x3f3f3f3f; const LL LNF = 1e16; const double inf = 0x3f3f3f3f3f3f; const double PI = acos(-1.0); const double eps = 1e-8; const int maxn = 10 + 5; const int mod = 100000000; const int dr[] = {-1, 0, 1, 0}; const int dc[] = {0, 1, 0, -1}; const char *de[] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"}; int n, m; const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; inline bool is_in(int r, int c){ return r >= 0 && r < n && c >= 0 && c < m; } struct Node{ int to, c, p, r, next; Node(){ } Node(int t, int cc, int pp, int rr, int n) : to(t), c(cc), p(pp), r(rr), next(n) { } }; Node a[maxn*2]; int head[maxn], cnt; void add_edge(int u, int v, int c, int p, int r){ a[cnt] = Node(v, c, p, r, head[u]); head[u] = cnt++; } struct State{ int state, pos; State(int s, int p) : state(s), pos(p) { } }; int dp[1<<10][10]; int vis[10]; int bfs(){ queue<State> q; int ans = INF; q.push(State(0, 0)); memset(dp, INF, sizeof dp); memset(vis, 0, sizeof vis); dp[0][0] = 0; while(!q.empty()){ State u = q.front(); q.pop(); int state = u.state; if(u.pos + 1 == n){ ans = min(ans, dp[state][u.pos]); continue; } for(int i = head[u.pos]; ~i; i = a[i].next){ int v = a[i].to; int c = a[i].c; int r = a[i].r; int p = a[i].p; if(vis[v] > 50) continue; ++vis[v]; dp[state|(1<<v)][v] = min(dp[state|(1<<v)][v], dp[state][u.pos] + ((state&(1<<c)) ? p : r)); q.push(State(state|(1<<v), v)); } } return ans; } int main(){ while(scanf("%d %d", &n, &m) == 2){ cnt = 0; memset(head, -1, sizeof head); for(int i = 0; i < m; ++i){ int u, v, c, p, r; scanf("%d %d %d %d %d", &u, &v, &c, &p, &r); add_edge(u-1, v-1, c-1, p, r); } int ans = bfs(); if(ans == INF) printf("impossible\n"); else printf("%d\n", ans); } return 0; }
相关文章
- hdu4901 枚举状态(找集合对S(xor) ==T(and))
- hdu4909 状态压缩(偶数字符子串)
- POJ1324贪吃蛇(状态压缩广搜)
- POJ2688状态压缩(可以+DFS剪枝)
- 3690状态压缩+暴力
- 【arc093f】Dark Horse(容斥原理,动态规划,状态压缩)
- 【BZOJ5299】【CQOI2018】解锁屏幕(动态规划,状态压缩)
- 状态压缩dp poj 3254 hdu5045
- 生成的代码如何存储内部信号、状态和参数数据
- 【状态设计优化DP】P4310 绝世好题
- Powerline:给 Vim 和 Bash 提供更棒的状态行和提示信息
- HTTP状态码详解
- HDU 4336 Card Collector (期望DP+状态压缩 或者 状态压缩+容斥)
- H3C 显示RIP当前运行状态及配置信息
- netstat - 显示网络连接,路由表,接口状态,伪装连接,网络链路信息和组播成员组。
- PHP实现用户在线状态检测
- 设计模式-状态模式
- Delphi 判断按键状态
- Light OJ 1406 Assassin`s Creed 状态压缩DP+强连通缩点+最小路径覆盖
- HDU 1429--胜利大逃亡(续)【BFS && 状态压缩】
- 状态压缩动态规划 -- 旅行商问题
- 基于switch case语句的Unity中用于状态切换的FiniteStateMachine(FSM)
- tcp连接的状态变迁以及如何调整tcp连接中处于time_wait的时间
- 【bzoj3312】[Usaco2013 Nov]No Change 状态压缩dp+二分
- 【bzoj1688】[USACO2005 Open]Disease Manangement 疾病管理 状态压缩dp+背包dp