题目链接:K-[JLOI2011]飞行路线_WUT2021校内训练⑦ (nowcoder.com)
题意请看原题,是中文的。
思路
本题突破口在K <= 10,且N <= 1e4。
设起点s, 终点t。
一般的最短路的题目都是建立一个二维图,这里我们建立一个K层的三维图,从第 0 层开始,第 i 层表示用了 i 次免费航线。这样最后统计所有t + N * i(0 <= i <= K)的点到源点的距离的最小值即可。
建图使用了一维拓展的方式,[0, N - 1]表示第一层,[N, 2 * N - 1]表示第二层,以此类推。
需要注意的是,建图的时候,需要给每一层的二维图都建立起边,并且将相邻的两层之间建立权值为0的免费航线。具体实现方法看代码。
代码
/*Copyright (C) Eriktse 2022*/ #include <iostream> #include <cstdio> #include <stack> #include <queue> #include <cmath> #include <cstring> #include <string> #include <vector> #include <map> #include <bitset> #include <utility> #define fi first #define se second #define gc getchar #define pr printf #define pb push_back #define sc scanf #define int long long //用%lld输出long long类型数据 using namespace std; inline int readInt() { int s = 0,w = 1;char c = gc(); while(c < '0' || c > '9'){if(c == '-')w = -1;c = gc();} while('0' <= c && c <= '9'){s = s * 10 + c - '0',c = gc();} return s * w; } /*--------全局变量--------*/ const int maxn = 1e5 + 2e4 + 10,inf = 1e15; int N, M, K, s, t; struct Node { int x, d; bool operator < (const Node &m)const{return d > m.d;} }; vector<Node> g[maxn]; int dist[maxn]; /*--------自定义函数-------*/ inline bool dijkstra(int s,int t) { memset(dist, 127, sizeof dist); priority_queue<Node> pq; pq.push({s, 0}); while(!pq.empty()) { int x = pq.top().x; int d = pq.top().d; pq.pop(); if(x == t)return 1; if(d > dist[x])continue; for(auto i : g[x]) if(d + i.d < dist[i.x])pq.push({i.x, dist[i.x] = d + i.d}); } return 0; } signed main() { N = readInt(), M = readInt(), K = readInt(); s = readInt(), t = readInt(); while(M --) { int x = readInt(), y = readInt(), w = readInt(); for(int i = 0;i <= K; ++ i) { g[x + N * i].pb({y + N * (i + 1), 0}); g[y + N * i].pb({x + N * (i + 1), 0}); g[x + N * i].pb({y + N * i, w}); g[y + N * i].pb({x + N * i, w}); } } dijkstra(s, t); int ans = inf; for(int i = 0;i <= K; ++ i)ans = min(ans, dist[t + N * i]); pr("%lld\n",ans); return 0; }
Comments NOTHING