简化版题意：给出 (n) 个点 (m) 条边的无向图，可以交换任意两条边的权值 (k) 次，求 (1) 结点到 (n) 结点的最短路。
考虑( ext{DP})。
把所有的边从小到大排序，那么贪心的做的话，肯定有一个分界线 (L) ，使得 (L) 前面的边全部被使用，后面的边都不会被选用，我们枚举这个分界线 (L)。
设 (dp_{i,j,k}) 表示当前是 (i) 结点，使用了前 (L) 条边的 (j) 条，用了 (k) 次魔法。
可以在( ext{Dijkstra})跑最短路时转移状态。
于是 ( ext{DP}) 时出现了两种情况。
对于当前权值为 (w) 的边 ((u, v))：
-
这条边是前 (L) 条边中的一条：
- (dp_{v,j + 1,k} = min(dp_{v,j + 1,k}, dp_{u,j,k} + w))。
- 因为这条边和第 (j + 1) 条边一定会被选用，为了方便枚举，我们从小到大选用。
-
这条边不是前 (L) 条边中的一条：
- (dp_{v,j,k} = min(dp_{v,j,k}, dp_{u,j,k} + w)) 直接使用这条边；
- (dp_{v,j + 1,k + 1} = min(dp_{v,j + 1,k + 1}, dp_{u,j,k} + w_{j + 1}))将这条边与第 (j + 1) 条边交换 。
代码写起来比较复杂。
#include <bits/stdc++.h>
#define DEBUG fprintf(stderr, "Passing [%s] line %d
", __FUNCTION__, __LINE__)
#define itn int
#define gI gi
using namespace std;
inline int gi()
{
int f = 1, x = 0; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return f * x;
}
const int maxn = 166;
int n, m, k, tot, head[maxn], ver[maxn * 2], nxt[maxn * 2], edge[maxn * 2];
int dp[55][maxn][55], in[55][maxn][55], ans = 1000000007;
inline void add(int u, int v, int w)
{
ver[++tot] = v, edge[tot] = w, nxt[tot] = head[u], head[u] = tot;
}
struct Node
{
int u, v, w;
} e[maxn];
struct QwQ
{
int u, j, k;
} ;
vector <int> vv[maxn];
inline bool cmp(Node x, Node y) {return x.w < y.w;}
inline void solve(int l)
{
queue <QwQ> q;
memset(dp, 0x3f, sizeof(dp));
memset(in, 0, sizeof(in));
in[1][0][0] = 1;
dp[1][0][0] = 0;
q.push((QwQ){1, 0, 0});
while (!q.empty())
{
int u = q.front().u, j = q.front().j, kk = q.front().k;
q.pop(); in[u][j][kk] = 0;
for (int i = vv[u].size() - 1; i >= 0; i-=1)
{
int now = vv[u][i], v;
if (u == e[now].u) v = e[now].v;
else v = e[now].u;
if (now <= l)
{
if (j < l && dp[v][j + 1][kk] > dp[u][j][kk] + e[j + 1].w)
{
dp[v][j + 1][kk] = dp[u][j][kk] + e[j + 1].w;
if (!in[v][j + 1][kk])
{
in[v][j + 1][kk] = 1;
q.push((QwQ){v, j + 1, kk});
}
}
}
else
{
if (j < l && kk < k && dp[v][j + 1][kk + 1] > dp[u][j][kk] + e[j + 1].w)
{
dp[v][j + 1][kk + 1] = dp[u][j][kk] + e[j + 1].w;
if (!in[v][j + 1][kk + 1])
{
in[v][j + 1][kk + 1] = 1;
q.push((QwQ){v, j + 1, kk + 1});
}
}
if (dp[v][j][kk] > dp[u][j][kk] + e[now].w)
{
dp[v][j][kk] = dp[u][j][kk] + e[now].w;
if (!in[v][j][kk])
{
in[v][j][kk] = 1;
q.push((QwQ){v, j, kk});
}
}
}
}
}
for (int i = 0; i <= k; i+=1) ans = min(ans, dp[n][l][i]);
}
int main()
{
//freopen(".in", "r", stdin);
//freopen(".out", "w", stdout);
n = gi(), m = gi(), k = gi();
for (int i = 1; i <= m; i+=1)
{
e[i].u = gi(), e[i].v = gi(), e[i].w = gi();
}
sort(e + 1, e + 1 + m, cmp);
for (int i = 1; i <= m; i+=1)
vv[e[i].u].push_back(i), vv[e[i].v].push_back(i);
for (int i = 0; i <= m; i+=1) solve(i);
printf("%d
", ans);
return 0;
}