分层图:
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10, M = 2.5e6 + 10;
typedef pair<int, int> PII;
#define fi first
#define se second
int h[N];
int e[M];
int ne[M];
int w[M];
int idx;
int n, m, k;
int s, t;
int dist[N];
bool st[N];
void add(int a, int b, int c)
{
e[idx] = b;
ne[idx] = h[a];
w[idx] = c;
h[a] = idx++;
}
void dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[s] = 0;
priority_queue<PII, vector<PII>,greater<PII>> heap;
heap.push({dist[s], s});
while (heap.size())
{
auto t = heap.top();
heap.pop();
int a = t.se;
if (st[a])
{
continue;
}
st[a] = true;
for (int i = h[a]; ~i; i = ne[i])
{
int j = e[i];
int v = max(dist[a],w[i]);//求路径中的最长边
//这里更新的是,到达同样一个点时,不同路径中长度最短的最长边
if (dist[j] > v)
{
dist[j] = v;
heap.push({dist[j], j});
}
}
}
}
int main()
{
memset(h, -1, sizeof h);
cin >> n >> m >> k;
s = 1;
t = n;
for (int i = 1; i <= m; i++)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
add(b, a, c);
for (int j = 1; j <= k; j++)
{
add(a + n * (j - 1), b + n * j, 0);
add(b + n * (j - 1), a + n * j, 0);
add(a + n * j, b + n * j, c);
add(b + n * j, a + n * j, c);
}
}
for (int i = 1; i <= k; i++)
{
add(t + n * (i - 1), t + n * i, 0);
}
dijkstra();
if(dist[t + n * k] == 0x3f3f3f3f)
{
cout<<-1<<endl;
return 0;
}
printf("%d", dist[t + n * k]);
return 0;
}