思路：
分层最短路的实质是dp思想 + 最短路。
在跑最短路的过程中，我们可以选择将某一条边的代价变成零，但是最多只能使用k次
dis[i][j]表示到达点i使用j次免费机会的最小代价
这样就有状态转移方程 dp[i][j] = min(dp[from][j] + val(from , i) , dp[from][j - 1]);
因此我们再进行松弛操作的时候就有
if(dis[i][j] + val(i , to) < dis[to][j]) dis[to][j] = dis[i][j] + val(i , to);
if(dis[j][j] < dis[to][j + 1] && j < k) dis[to][j + 1] = dis[i][j];
AC代码：
1 #include<cstdio> 2 #include<string.h> 3 #include<algorithm> 4 #include<cmath> 5 #include<iostream> 6 #include<vector> 7 #include<queue> 8 #include<set> 9 #include<map> 10 #include<cctype> 11 #define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) 12 #define mem(a,x) memset(a,x,sizeof(a)) 13 #define lson rt<<1,l,mid 14 #define rson rt<<1|1,mid + 1,r 15 #define P pair<int,int> 16 #define ull unsigned long long 17 using namespace std; 18 typedef long long ll; 19 const int maxn = 1e6 + 10; 20 const ll mod = 998244353; 21 const int inf = 0x3f3f3f3f; 22 const long long INF = 0x3f3f3f3f3f3f3f3f; 23 const double eps = 1e-7; 24 inline ll read() 25 { 26 ll X = 0, w = 0; char ch = 0; 27 while (!isdigit(ch)) { w |= ch == '-'; ch = getchar(); } 28 while (isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar(); 29 return w ? -X : X; 30 } 31 int n, m, k; 32 33 struct Edge { 34 ll to, val, next; 35 }edge[maxn]; 36 int cnt = 0; 37 int head[maxn]; 38 void add(int u, int v, int val) 39 { 40 edge[++cnt].to = v, edge[cnt].val = val, edge[cnt].next = head[u], head[u] = cnt; 41 } 42 struct node 43 { 44 ll index, dist, j; 45 bool operator < (const node& x) const 46 { 47 return dist > x.dist; 48 } 49 }; 50 ll dis[maxn][11]; 51 ll vis[maxn][11]; 52 void init() 53 { 54 for (int i = 0; i < maxn; ++i) 55 { 56 for (int j = 0; j <= k; ++j) 57 { 58 dis[i][j] = INF, vis[i][j] = 0; 59 } 60 } 61 } 62 inline void Dj(int s) 63 { 64 dis[s][0] = 0; 65 priority_queue<node>que; 66 que.push(node{ s , 0 , 0 }); 67 while (que.size()) 68 { 69 node tmp = que.top(); que.pop(); 70 ll from = tmp.index; 71 ll dist = tmp.dist; 72 ll j = tmp.j; 73 if (vis[from][j]) continue; 74 vis[from][j] = 1; 75 for (int i = head[from]; i != -1; i = edge[i].next) 76 { 77 ll to = edge[i].to; 78 if (dis[from][j] + edge[i].val < dis[to][j]) 79 { 80 dis[to][j] = dis[from][j] + edge[i].val; 81 que.push(node{ to , dis[to][j] , j }); 82 } 83 if (j < k && dis[from][j] < dis[to][j + 1]) 84 { 85 dis[to][j + 1] = dis[from][j]; 86 que.push(node{ to , dis[to][j + 1] , j + 1 }); 87 } 88 } 89 } 90 91 } 92 93 94 int main() 95 { 96 int T; 97 T = read(); 98 while (T--) 99 { 100 mem(head, -1); 101 ll ans = INF; 102 n = read(), m = read(), k = read(); 103 for (int i = 1; i <= m; ++i) 104 { 105 int u = read(), v = read(), val = read(); 106 add(u, v, val); 107 } 108 init(); 109 Dj(1); 110 for (int i = 0; i <= k; ++i) 111 { 112 ans = min(ans, dis[n][i]); 113 } 114 cout << ans << endl; 115 } 116 117 return 0; 118 } 119 120 /* 121 样例输入： 122 1 123 5 6 1 124 1 2 2 125 1 3 4 126 2 4 3 127 3 4 1 128 3 5 6 129 4 5 2 130 样例输出： 131 3 132 */