标程（记忆化搜索）

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 5e4 + 5;
vector<pair<int, ll>> G[N];
int n, m, K;
ll f[N][15];

ll dfs(int x, int k) {
    if (f[x][k]) return f[x][k];
    
    for (auto i : G[x]) { // 若当前选择没有失误，就选最大的
        int y = i.first, w = i.second;
        f[x][k] = max(f[x][k], dfs(y, k) + w);
    }
    if (k) {
        for (auto i : G[x]) { // 若当前失误，就选最小的
            int y = i.first, w = i.second;
            f[x][k] = min(f[x][k], dfs(y, k - 1) + w);
        }
    }
    return f[x][k];
}

int main() {
    scanf("%d%d%d", &n, &m, &K);
    for (int i = 1, x, y, c; i <= m; i++) {
        scanf("%d%d%d", &x, &y, &c);
        G[x].push_back({y, c});
    }

    printf("%lld\n", dfs(1, K));
    return 0;
}

错误程序（dijkstral），看看为什么错

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 5e4 + 5;
vector<pair<int, ll>> G[N];
struct node {
    ll x; int y, z;
    bool operator<(const node& b) const { return x < b.x; }
};
int n, m, K;
ll dis[N][15]; bool v[N][15];

void dijkstra() {
    memset(dis, -1, sizeof(dis)); dis[1][0] = 0;
    memset(v, 0, sizeof(v));
    priority_queue<node> q; q.push({0, 1, 0});
    while (!q.empty()) {
        int x = q.top().y, k = q.top().z; q.pop();
        if (v[x][k]) continue; v[x][k] = 1;
        for (auto i : G[x]) {
            int y = i.first, w = i.second;
            
            if (dis[y][k] == -1 || dis[y][k] < dis[x][k] + w) {
                dis[y][k] = dis[x][k] + w;
                q.push({dis[y][k], y, k});
            }
            if (k < K)
            if (dis[y][k + 1] == -1 || dis[y][k + 1] > dis[x][k] + w) {
                dis[y][k + 1] = dis[x][k] + w;
                q.push({dis[y][k + 1], y, k + 1});
            }
        }
    }
}

int main() {
    scanf("%d%d%d", &n, &m, &K);
    for (int i = 1, x, y, c; i <= m; i++) {
        scanf("%d%d%d", &x, &y, &c);
        G[x].push_back({y, c});
    }
    dijkstra();
    printf("%lld\n", dis[n][K]);
    return 0;
}

标程（记忆化搜索）：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 5e4 + 5;
vector< pair<int ,ll > >G[N];
int n, m, K;
ll f[N][15];
ll dfs(int x, int k)
{
	if (f[x][k]) return f[x][k];
	
	for (auto i:G[x])//若当前选择没有失误，就选最大的
    {
		int y=i.first,w=i.second;
		f[x][k] = max(f[x][k], dfs(y, k)+w);
	}
	if(k)
    {
        for (auto i:G[x])//若当前失误，就选最小的
        {
            int y=i.first,w=i.second;
            f[x][k] = min(f[x][k], dfs(y, k-1)+w);
        }
	}
	return f[x][k];
}

int main()
{
	scanf("%d%d%d",&n,&m,&K);
	for (int i = 1,x,y,c; i <= m; i++)
		scanf("%d%d%d",&x,&y,&c),
        G[x].push_back({y,c});

	printf("%lld\n",dfs(1, K));
	return 0;
}

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 5e4 + 5;
vector< pair<int ,ll > >G[N];
struct node
{
    ll x;int y, z;
    bool operator< (const node &b) const {return x<b.x;}
};
int n, m, K;
ll dis[N][15];bool v[N][15];
void  dijkstra()
{
    memset(dis, -1, sizeof(dis));dis[1][0]=0;
    memset(v, 0, sizeof(v));
	priority_queue<node> q; q.push({0, 1, 0});
    while(!q.empty())
    {
        int x=q.top().y, k=q.top().z; q.pop();
        if(v[x][k]) continue; v[x][k]=1;
        for(auto i: G[x])
        {
            int y=i.first, w=i.second;
        if(dis[y][k]==-1 || dis[y][k]&lt;dis[x][k]+w)
        {
            dis[y][k]=dis[x][k]+w;
            q.push({dis[y][k], y, k});
        }
        if(k&lt;K)
        if(dis[y][k+1]==-1 || dis[y][k+1]&gt;dis[x][k]+w)
        {
            dis[y][k+1]=dis[x][k]+w;
            q.push({dis[y][k+1], y, k+1});
        }
    }
}

}
int main()
{
scanf("%d%d%d",&n,&m,&K);
for (int i = 1,x,y,c; i <= m; i++)
scanf("%d%d%d",&x,&y,&c),
G[x].push_back({y,c});
dijkstra();
printf("%lld\n",dis[n][K]);
return 0;
}