题面

简化版题意：给出 \(n\) 个点 \(m\) 条边的无向图，可以交换任意两条边的权值 \(k\) 次，求 \(1\) 结点到 \(n\) 结点的最短路。

考虑\(\text{DP}\)。

把所有的边从小到大排序，那么贪心的做的话，肯定有一个分界线 \(L\) ，使得 \(L\) 前面的边全部被使用，后面的边都不会被选用，我们枚举这个分界线 \(L\)。

设 \(dp_{i,j,k}\) 表示当前是 \(i\) 结点，使用了前 \(L\) 条边的 \(j\) 条，用了 \(k\) 次魔法。

可以在\(\text{Dijkstra}\)跑最短路时转移状态。

于是 \(\text{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\n", __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\n", ans);
    return 0;
}