题目链接: https://www.luogu.org/problemnew/show/P4568
卡了一晚上, 算是分层图最短路的模板. 注意卡 SPFA, 所以我写了个 SLF 优化.
同时 AC400 祭!~
- #include <queue>
- #include <cstdio>
- #include <cstring>
- #include <iostream>
- #include <algorithm>
- #define ri register
- using namespace std;
- const int maxn = 200000 + 10;
- const int inf = 2147483647;
- inline int read()
- {
- int k=0,f=1;
- char c=getchar();
- while(!isdigit(c))
- {
- if(c=='-')f=-1;
- c=getchar();
- }
- while(isdigit(c))
- {
- k=(k<<1)+(k<<3)+c-48;
- c=getchar();
- }
- return k*f;
- }
- int n, m, k, s, end, dis[maxn][20];
- bool vis[maxn][20];
- struct edge{
- int from, len, to, next;
- }e[maxn<<2];
- int head[maxn], cnt = 0;
- struct que{
- int a, b;
- };
- deque<que> q;
- inline void add(int u, int v, int w)
- {
- e[++cnt].from = u;
- e[cnt].to = v;
- e[cnt].len = w;
- e[cnt].next = head[u];
- head[u] = cnt;
- }
- inline void SPFA()
- {
- memset(dis, 127, sizeof(dis));
- memset(vis, 0, sizeof(vis));
- q.push_back((que){s,0});
- dis[s][0] = 0;
- vis[s][0] = 1;
- while(!q.empty())
- {
- que now = q.front(); q.pop_front();
- vis[now.a][now.b] = 0;
- for(ri int i = head[now.a]; i != -1; i = e[i].next)
- {
- if(dis[e[i].to][now.b]> dis[now.a][now.b] + e[i].len)
- {
- dis[e[i].to][now.b] = dis[now.a][now.b] + e[i].len;
- if(vis[e[i].to][now.b] == 0)
- {
- vis[e[i].to][now.b] = 1;
- if(q.empty() || dis[e[i].to][now.b]> dis[q.front().a][now.b])
- q.push_back((que){e[i].to, now.b});
- else
- q.push_front((que){e[i].to, now.b});
- }
- }
- if(now.b + 1 <= k)
- {
- if(dis[e[i].to][now.b + 1]> dis[now.a][now.b])
- {
- dis[e[i].to][now.b + 1] = dis[now.a][now.b];
- if(vis[e[i].to][now.b + 1] == 0)
- {
- vis[e[i].to][now.b + 1] = 1;
- if(q.empty() || dis[e[i].to][now.b]> dis[q.front().a][now.b + 1])
- q.push_back((que){e[i].to, now.b + 1});
- else
- q.push_front((que){e[i].to, now.b + 1});
- }
- }
- }
- }
- }
- }
- int main()
- {
- //freopen(".in","r",stdin);
- //freopen(".out","w",stdout);
- memset(head, -1, sizeof(head));
- n = read(); m = read(); k = read(); s = read(); end = read();
- for(ri int i = 1; i <= m; i++)
- {
- int u, v, w;
- u = read(); v = read(); w = read();
- add(u, v, w); add(v, u, w);
- }
- SPFA();
- printf("%d",dis[end][k]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2689301.html