题意:n个点，m条单向边，可以让k条边距离为0，求1到n的最短路。
分层图最短路的裸题，拆成k+1层，表示已经消耗j次使边距离为0（0<=j<=k）, 即每个点拆成k个点
#include <bits/stdc++.h>
using namespace std;
#define MP(X, Y) make_pair(X, Y)
#define PII pair<int, int>
#define X first
#define Y secondusing namespace fastIO;
#define N 4000000
#define ll long long
#define INF 0x3f3f3f3f
struct EdegeNode{int v;ll w;int next;}edge[N*2+100];
struct Node {int v;ll sum;bool operator < (const Node &a) const {return sum > a.sum;}
}node;
int head[N+100];
bool vis[N+100];
ll dis[N+100];
int n,k,m;
int cut;
void addedge(int u,int v,ll w)
{edge[++cut].w=w;edge[cut].v=v;edge[cut].next=head[u];head[u]=cut;
}
void dijkstra()
{priority_queue <Node> q;for(int i = 0; i <= (n)*(k+1); ++i)dis[i] = (ll)INF*10000;memset(vis, 0, sizeof(vis));dis[1] = 0;q.push(Node{1, 0});vis[1] = 1;while(!q.empty()) {node = q.top();int u = node.v;q.pop();vis[u] = 0;for(int i = head[u]; ~i; i = edge[i].next) {int v = edge[i].v;if(dis[u]+edge[i].w<dis[v]) {dis[v] = dis[u] + edge[i].w;if(!vis[v]) {vis[v] = 1;q.push(Node{v, dis[v]});}}}}
}
int main ()
{int T, u, v;ll w;scanf("%d", &T);while(T--) {cut = 0;memset(head, -1, sizeof(head));scanf("%d%d%d", &n, &m, &k);for(int i = 1; i <= m; ++i) {scanf("%d%d%lld", &u, &v, &w);for(int j = 0; j <= k; ++j) {addedge(u + j*n, v + j*n, w);if(j != k) {addedge(u+j*n, v + (j+1)*n, 0);}}}dijkstra();ll ans = (ll)INF*100000;for(int i = 0; i <= k; ++i) {ans = min(ans, dis[i*n+n]);}printf("%lld\n", ans);}return 0;
}