P4568 [JLOI2011] 飞行路线

news/2024/7/15 19:48:53 标签: 图论

时间复杂度 O(k * (n + m))

注意存边的数组大小，除了 k * m个边外，还有上下层之间的边，数组再开大点就行。（不然会re tle

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <random>
#include <sstream>
#include <numeric>
#include <stdio.h>
#include <functional>
#include <bitset>
#include <algorithm>
using namespace std;

// #define Multiple_groups_of_examples
#define IOS std::cout.tie(0);std::cin.tie(0)->sync_with_stdio(false);
#define dbgnb(a) std::cout << #a << " = " << a << '\n';
#define dbgtt cout<<" !!!test!!! "<<endl;
#define rep(i,x,n) for(int i = x; i <= n; i++)

#define all(x) (x).begin(),(x).end()
#define pb push_back
#define vf first
#define vs second

typedef long long LL;
typedef pair<int,int> PII;

const int INF = 0x3f3f3f3f;
const int N = 3e6 + 21;
int e[N], ne[N], w[N], h[N], idx;
bool vis[N];
int dist[N];
void add(int u, int v, int a) {
	e[idx] = v, ne[idx] = h[u], w[idx] = a, h[u] = idx++;
}
void inpfile();
void solve() {
	int n,m,k; cin>>n>>m>>k;
	int st,ed; cin>>st>>ed;
	st++; ed++;
	memset(h, -1, sizeof(h));
	rep(i,1,m) {
		int u,v,a; cin>>u>>v>>a;
		u++; v++;
		add(u,v,a);
		add(v,u,a);
		rep(j,1,k) {
			// 每一层处理
			add(u + j * n, v + j * n, a);
			add(v + j * n, u + j * n, a);
			// 层与层
			add(u + (j-1) * n, v + j * n, 0);
			add(v + (j-1) * n, u + j * n, 0);
		}
	}
	priority_queue<PII> heap;
	heap.push({0,st});
	memset(dist, 0x3f, sizeof(dist));
	dist[st] = 0;
	// cout<<dist[st]<<endl;
	while(heap.size()) {
		auto tmp = heap.top(); heap.pop();
		int ver = tmp.vs, distance = -tmp.vf;
		if(vis[ver]) continue;
		vis[ver] = 1;
		for(int i = h[ver]; ~i; i = ne[i]) {
			int y = e[i];
			if(dist[y] > distance + w[i]) {
				dist[y] = distance + w[i];
				heap.push({-dist[y],y});
			}
		}
	}
	int mi = INF;
	// cout<<dist[st];
	// rep(i,1,n) cout<<dist[i]<<" ";
	rep(i,0,k) mi = min(mi, dist[ed + i * n]);
	cout<<mi;
}
int main()
{
	#ifdef Multiple_groups_of_examples
	int T; cin>>T;
	while(T--)
	#endif
	solve();
	return 0;
}
void inpfile() {
	#define mytest
	#ifdef mytest
	freopen("ANSWER.txt", "w",stdout);
	#endif
}