Problem

Code

#include "bits/stdc++.h"
using namespace std ;
struct Node
{
	int num, dis ;
	friend bool operator <(Node a, Node b)
	{
		return a.dis > b.dis ;
	}
} ;
const int N = 100010 ;
int n, m, k, dis[N << 6], ans = 0x3f3f3f3f ;
priority_queue<Node> q ;
int weight[N << 8], head[N << 8], to[N << 8], pre[N << 8], vis[N], cnt ;
void add(int u, int v, int w)
{
	pre[++cnt] = head[u], head[u] = cnt ;
	to[cnt] = v, weight[cnt] = w ;
}
void dij()
{
	memset(dis, 0x3f, sizeof(dis)) ;
	q.push(Node{1, 0}) ;
	dis[1] = 0 ;
	while(!q.empty())
	{
		Node u = q.top() ; q.pop() ;
		if(vis[u.num]) continue ;
		for(int v = head[u.num] ; v ; v = pre[v])
		{
			if(dis[to[v]] > dis[u.num] + weight[v])
			{
				dis[to[v]] = dis[u.num] + weight[v] ;
				q.push((Node){to[v], dis[to[v]]}) ;
			}
		}
	}
}
int main()
{
//	freopen("D:/GPT浏览器下载/P2939_2.in", "r", stdin) ;
	ios::sync_with_stdio(false) ;
	cin.tie(0) ; cout.tie(0) ;
	cin >> n >> m >> k ;
	for(int i = 1, u, v, w ; i <= m ; ++i)
	{
		cin >> u >> v >> w ;
		add(u, v, w), add(v, u, w) ;
		for(int j = 1 ; j <= k ; ++j)
		{
			add(n * j + u, n * j + v, w) ;
			add(n * j + v, n * j + u, w) ;       // 建立 u <-> v 未升级
			add(n * (j - 1) + u, n * j + v, 0) ; // 建立 u -> v 已升级
			add(n * (j - 1) + v, n * j + u, 0) ; // 建立 v -> u 已升级
		}
	}
	dij() ;
	for(int i = 0 ; i <= k ; ++i)
	{
		ans = min(ans, dis[n * i + n]) ;
	}
	cout << ans ;
	return 0 ;
}