题目大意：

在一个无向图中找出一条1到n的路径，我们可以选择K条边使其权值变为0，我们的目的是使得路径上第K+1大的边最小

解题思路：

解法一：

我们用dp的思想

dis[x][p]表示1到x中已经指定p条边权值为0，我们用SPFA对其进行转移，也就是说我们会从dis[x][p]中转移出两个状态：dis[y][p] 和 dis[y][p+1]

怎么转移？

$$因为dis[y][p]表示的是1到y中已经指定p条边权值为0$$

$$所以我们可以得出dis[y][p]=min(dis[y][p],max(dis[x][p],len[i]))$$

$$同理$$

$$dis[y][p+1]=min(dis[y][p+1],dis[x][p]);$$

当然，因为我们每个满足条件的点都是需要入栈的

所以我们并不能用min，我们需要用if去判断

上面只是为了方便

解法二：

因为我最近专攻最短路，所以就不细讲

主要思路：二分+spfa

将问题转换为是否存在一条合法的路径，使得花费不超过mid

这样我们只需要把花费大于mid的边看做长度为1的边，把花费不超过mid的边看做长度为0的边，然后求1到N的最短路是否不超过K即可。可以用双端队列BFS求解这种边全只有0&1的最短路问题

加粗部分摘自《算法竞赛进阶指南》(李煜东)

Accepted code:

#include
    
     #include
     
      #include
      
       #define rri register intusing namespace std;const int inf = 1e9;const int N = 1005;const int P = 10005; struct edge {
    	int to, d, next;}e[P<<1];struct dp {
    	int from, p;	dp(int x, int y) {
    		from = x; p = y;	}	void change(int x, int y) {
    		from = x; p = y;	}};int cnt, n, p, k, x, y, w;int dis[N][P], v[N][P], last[N];inline void add(int x, int y, int w) {
    	e[++cnt].to = y; e[cnt].d = w; e[cnt].next = last[x]; last[x] = cnt;	e[++cnt].to = x; e[cnt].d = w; e[cnt].next = last[y]; last[y] = cnt;}void spfa() {
    	for (rri i = 0; i <= n; i++)		for (rri j = 0; j <= p; j++)			dis[i][j] = inf, v[i][j] = 0;	dp a(1, 0);	queue 
       
         q; q.push(a);	v[1][0] = 1; dis[1][0] = 0;	while (!q.empty()) {
    		a = q.front(); q.pop();		int x = a.from, pn = a.p;		v[x][pn] = 0;		for (rri i = last[x]; i; i = e[i].next) {
    			int y = e[i].to;			if (max(e[i].d, dis[x][pn]) < dis[y][pn]) {
    				dis[y][pn] = max(e[i].d, dis[x][pn]);				if (!v[y][pn]) {
    					v[y][pn] = 1;					a.change(y, pn);					q.push(a);				}			}			if (pn < k && dis[x][pn] < dis[y][pn+1]) {
    				dis[y][pn+1] = dis[x][pn];				if (!v[y][pn+1]) {
    					v[y][pn+1] = 1;					a.change(y, pn+1);					q.push(a);				}			}		}	}}int main() {
    	scanf("%d %d %d", &n, &p, &k);	for (rri i = 1; i <= p; i++)		scanf("%d %d %d", &x, &y, &w),		add(x, y, w);	spfa();	if (dis[n][k] == inf) printf("-1\n");	else printf("%d\n", dis[n][k]);}