分层图最短路.
把每个点拆成 \(k+1\) 个点, 表示总共有 \(k+1\) 层.
然后每层正常连边,
若 \((u,v)\) 有边, 则把每一层的 \(u\) 和下一层的 \(v\), 每一层的 \(v\) 和下一层的 \(u\) 连边.
然后跑最短路就行了, 终点是最后一层的 \(t\).
- #include <cstdio>
- #include <queue>
- #include <algorithm>
- using namespace std;
- int xjc; char ch;
- inline int read(){
- xjc = 0; ch = getchar();
- while(ch <'0' || ch> '9') ch = getchar();
- while(ch>= '0' && ch <= '9'){ xjc = xjc * 10 + ch - '0'; ch = getchar(); }
- return xjc;
- }
- const int MAXN = 100010;
- const int MAXM = 500010;
- struct Edge{
- int next, to, dis;
- }e[MAXM <<2];
- int head[MAXN], num, dis[MAXN];
- inline void Add(int from, int to, int dis){
- e[++num] = (Edge){ head[from], to, dis }; head[from] = num;
- }
- typedef pair<int, int> point;
- priority_queue <point, vector<point>, greater<point>> q;
- point now;
- int n, m, k, s, t, a, b, c;
- int main(){
- n = read(); m = read(); k = read(); s = read(); t = read();
- for(int i = 1; i <= m; ++i){
- a = read(); b = read(); c = read();
- Add(a, b, c); Add(b, a, c);
- for(int j = 1; j <= k; ++j){ // 分层
- Add(a + (j - 1) * n, b + j * n, 0);
- Add(b + (j - 1) * n, a + j * n, 0);
- Add(a + j * n, b + j * n, c);
- Add(b + j * n, a + j * n, c);
- }
- }
- q.push(point(0, s));
- memset(dis, 127, sizeof dis);
- dis[s] = 0;
- while(q.size()){
- now = q.top(); q.pop();
- if(dis[now.second] <now.first) continue;
- for(int i = head[now.second]; i; i = e[i].next)
- if(dis[e[i].to]> dis[now.second] + e[i].dis){
- dis[e[i].to] = dis[now.second] + e[i].dis;
- q.push(point(dis[e[i].to], e[i].to));
- }
- }
- printf("%d\n", dis[t + k * n]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2807725.html