带依赖的多关键点求最短路问题

一.迪杰斯特拉算法模板using Pair pairint, int; const int N 1e5 10; const int INF 1e18; // 使用 long long 的最大值 int n, m, s, dis[N]; vectorPair G[N]; // 邻接表 void dijkstra(int x) { priority_queuePair, vectorPair, greaterPair q; for (int i 1; i n; i) { // 初始化为无穷大 dis[i] INF; } dis[x] 0; q.push({ 0, x });//初始距离0出发点x while (!q.empty()) { int u q.top().second;//取出当前距离最小的点u int current_dist q.top().first; q.pop(); if (current_dist dis[u]) continue; // 如果信息已经过时则丢弃 for (int i 0; i G[u].size(); i) {//遍历u的所有出边 int v G[u][i].first;//邻接点 int w G[u][i].second;//边权 //松弛操作u走这条边到v更短就更新 if (dis[u] w dis[v]) { dis[v] dis[u] w; q.push({ dis[v], v });//新距离入堆 } } } } signed main() { ios::sync_with_stdio(false); cin.tie(0); cin n m s;//几个顶点几条边起点 for (int i 0; i m; i) { int u, v, w; cin u v w; G[u].push_back({ v, w }); // 添加边 } dijkstra(s); for (int i 1; i n; i) { cout dis[i] \n; // s到每个点的距离 } return 0; }码蹄集OJ-宝玉的考验#includebits/stdc.h using namespace std; #define endl \n #define int long long int n,m,k,t; using Pair pairint, int; const int N 2e5 10; const int INF 1e18; // 使用 long long 的最大值 int dis[N][15];//到达u点经过关键点集合为mask的最短路 vectorPair G[N]; // 邻接表 struct Node { int d,u,mask;//距离当前点状态 bool operator(const Node t) const { return d t.d;//小根堆 } }; int id[N];//每个点是否是关键点是的话编号0~4 bool need[5][5];//依赖need[x][y]1表示要到y必须经过x void dijkstra(int x) { priority_queueNode q; for (int i 1; i n; i) { // 初始化为无穷大 for (int mask0;mask(1k);mask) { dis[i][mask] INF; } } dis[x][0] 0;//起点x一个关键点都没有经过mask0距离为0 q.push({ 0, x ,0}); while (!q.empty()) { //取出堆顶当前距离最短的状态 Node now q.top(); int dnow.d;//当前距离 int unow.u;//当前点 int masknow.mask;//当前关键点经过状态 q.pop(); if (d dis[u][mask]) continue; // 如果信息已经过时则丢弃 for (int i 0; i G[u].size(); i) { int v G[u][i].first; int w G[u][i].second; int new_maskmask;//先继承当前状态 //如果v是关键点 if (id[v]!-1) { int yid[v];//取出编号 bool oktrue; //检查所有前置约束要走y必须先走过所有x for (int x0;xk;x) { if (need[x][y]!(mask(1x))) { okfalse; break; } } //不满足约束不能走这条边 if (!ok) { continue; } //满足则把y加入状态 new_mask|1y; } if (dis[u][mask] w dis[v][new_mask]) { dis[v][new_mask] dis[u][mask] w; q.push({ dis[v][new_mask], v , new_mask });//将新点加入堆 } } } } void solve() { cinnmkt; for (int i0;in;i) { G[i].clear(); id[i]-1; } memset(need,0,sizeof(need)); for (int i 0; i m; i) { int u, v, w; cin u v w; G[u].push_back({ v, w }); // 添加边 G[v].push_back({ u, w }); } //读关键点 for (int i0;ik;i) { int x; cin x; id[x] i; } //读依赖 for (int i0;it;i) { int x,y; cin x y; need[id[x]][id[y]]1;//如果要到达y必须先经过x } dijkstra(1); int ansINF; for (int mask0;mask(1k);mask) { ansmin(ans, dis[n][mask]);//遍历n的每一种状态取最小值 } if (ansINF) {//到不了 coutimpossibleendl; } else { coutansendl; } } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cint; while (t--) solve(); return 0; }