luogu P4568 [JLOI2011]飞行路线

本文主要是介绍luogu P4568 [JLOI2011]飞行路线，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一道分层最短路

看看代码就懂分层最短路什么意思了

qq姐给我讲的w

不记得是gg多久前布置的题了

反正

很久不打代码

手指似乎都不会用了

好僵硬啊。。。

#include<cstdio>
#include<queue>
#define sev en
using namespace std;
#define INF 2147483647
#define N 10000010priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
struct EDGE{int nxt,to,w;
}e[N];
int head[N],vis[N],dis[N],cnt;void add(int x,int y,int z) {e[++cnt].to = y;e[cnt].w = z;e[cnt].nxt = head[x];head[x] = cnt;
}int main() {int n,m,k;scanf("%d%d%d",&n,&m,&k);int s,t;scanf("%d%d",&s,&t);for(int i = 1; i <= m; i++) {int a,b,c;scanf("%d%d%d",&a,&b,&c);add(a,b,c);add(b,a,c);for(int j = 1; j <= k; j++) {add(a + j * n,b + j * n,c);add(b + j * n,a + j * n,c);add(a + (j - 1) * n,b + j * n,0);add(b + (j - 1) * n,a + j * n,0);}}for(int i = 0; i <= n; i++)for(int j = 0; j <= k; j++)dis[i + j * n] = INF;dis[s] = 0;q.push(make_pair(0,s));while(!q.empty()) {int u = q.top().second;q.pop();if(vis[u])continue;vis[u] = 1;for(int i = head[u]; i; i = e[i].nxt) {int v = e[i].to;if(dis[v] > dis[u] + e[i].w) {dis[v] = dis[u] + e[i].w;q.push(make_pair(dis[v],v));}}}int ans = INF;for(int i = 0; i <= k; i++)ans = min(ans,dis[t + i * n]);printf("%d",ans);return 0;
}