一.迪杰斯特拉算法模板：
using Pair = pair<int, int>; const int N = 1e5 + 10; const int INF = 1e18; // 使用 long long 的最大值 int n, m, s, dis[N]; vector<Pair> G[N]; // 邻接表 void dijkstra(int x) { priority_queue<Pair, vector<Pair>, greater<Pair>> 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-宝玉的考验
#include<bits/stdc++.h> using namespace std; #define endl "\n" #define int long long int n,m,k,t; using Pair = pair<int, int>; const int N = 2e5 + 10; const int INF = 1e18; // 使用 long long 的最大值 int dis[N][1<<5];//到达u点，经过关键点集合为mask的最短路 vector<Pair> 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_queue<Node> q; for (int i = 1; i <= n; i++) { // 初始化为无穷大 for (int mask=0;mask<(1<<k);mask++) { dis[i][mask] = INF; } } dis[x][0] = 0;//起点x，一个关键点都没有经过（mask=0），距离为0 q.push({ 0, x ,0}); while (!q.empty()) { //取出堆顶（当前距离最短的状态） Node now = q.top(); int d=now.d;//当前距离 int u=now.u;//当前点 int mask=now.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_mask=mask;//先继承当前状态 //如果v是关键点 if (id[v]!=-1) { int y=id[v];//取出编号 bool ok=true; //检查所有前置约束：要走y，必须先走过所有x for (int x=0;x<k;x++) { if (need[x][y]&&!(mask&(1<<x))) { ok=false; break; } } //不满足约束，不能走这条边 if (!ok) { continue; } //满足则把y加入状态 new_mask|=1<<y; } 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() { cin>>n>>m>>k>>t; for (int i=0;i<=n;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 i=0;i<k;i++) { int x; cin >> x; id[x] =i; } //读依赖 for (int i=0;i<t;i++) { int x,y; cin >> x >> y; need[id[x]][id[y]]=1;//如果要到达y必须先经过x } dijkstra(1); int ans=INF; for (int mask=0;mask<(1<<k);mask++) { ans=min(ans, dis[n][mask]);//遍历n的每一种状态，取最小值 } if (ans==INF) {//到不了 cout<<"impossible"<<endl; } else { cout<<ans<<endl; } } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin>>t; while (t--) solve(); return 0; }
