pku 3635 Full Tank? 优先队列+BFS

野性酷女 2022-08-21 00:21 139阅读 0赞

用二维数组state\[C\]\[fuel\], 表示在城市C油量为fuel时的最小代价.

怎样在一个节点上进行状态转移?  
 1. 把该节点的油量加1, 以供继续拓展.  
2. 直接到其他可达节点.

注意:

1. 应使用优先队列(最小堆)优化搜索速度.

2. 用邻接表表示一个节点所有相邻的节点, 效率更高.

\#include <iostream> \#include <cstring> \#include <cstdio> \#include <queue> using namespace std; struct Edge\{ int to, dis; //to:　尾端节点, dis: 到尾端节点的距离 Edge\* next; \}; Edge\* adj\[1001\]; //邻接表的N个首节点 Edge edge\[20001\]; //所有的边（无向） int state\[1001\]\[101\]; //state\[C\]\[fuel\]: 在城市C油量为fuel时的最小价钱 int price\[1001\]; //price\[C\]: 城市C的油价 struct Node\{ int city, fuel, cost; Node(int \_city, int \_fuel, int \_cost) \{ city = \_city; fuel = \_fuel; cost = \_cost; \} bool operator<(const Node& r) const \{ return cost > r.cost; \} \}; int n, m, q; int max\_value, start, end; int bfs() \{ memset(state, 0x7f, sizeof(state)); priority\_queue<Node> q; q.push(Node(start, 0, 0)); state\[start\]\[0\] = 0; while(!q.empty()) \{ Node n = q.top(); if(n.city == end) //到达终点 break; if(n.cost != state\[n.city\]\[n.fuel\]) continue; q.pop(); //1. 把该节点的油量加1, 以供继续拓展(此节点push进queue后, 当pop出此节点可以再把油价加1...). //并更新最小代价值. if(n.fuel < max\_value && state\[n.city\]\[n.fuel\] + price\[n.city\] < state\[n.city\]\[n.fuel+1\]) \{ state\[n.city\]\[n.fuel+1\] = state\[n.city\]\[n.fuel\] + price\[n.city\]; q.push(Node(n.city, n.fuel+1, state\[n.city\]\[n.fuel+1\])); \} //2. 直接到其他可达节点. //并更新最小代价值. for(Edge\* ptr = adj\[n.city\]; ptr; ptr = ptr->next) \{ if(n.fuel >= ptr->dis && state\[n.city\]\[n.fuel\] < state\[ptr->to\]\[n.fuel-ptr->dis\]) \{ state\[ptr->to\]\[n.fuel-ptr->dis\] = state\[n.city\]\[n.fuel\]; q.push(Node(ptr->to, n.fuel-ptr->dis, state\[ptr->to\]\[n.fuel-ptr->dis\])); \} \} \} return state\[end\]\[0\]; \} int cnt; void add\_edge(int u, int v, int w) \{ Edge\* ptr = &edge\[cnt++\]; ptr->to = v; ptr->dis = w; ptr->next = adj\[u\]; adj\[u\] = ptr; \} int main() \{ scanf("%d%d", &n, &m); for(int i = 0; i < n; ++i) scanf("%d", &price\[i\]); int u, v, w; cnt = 0; memset(adj, 0, sizeof(adj)); for(int i = 0; i < m; ++i) \{ scanf("%d%d%d", &u, &v, &w); add\_edge(u, v, w); add\_edge(v, u, w); \} scanf("%d", &q); for(int i = 0; i < q; ++i) \{ scanf("%d%d%d", &max\_value, &start, &end); int ret = bfs(); if(ret < 0x7f7f7f7f) printf("%d/n", ret); else printf("impossible/n"); \} return 0; \}