题目描述：无向图，n个节点，m条边（有边权），让你选择一些边把1号节点和n号节点连接起来。其中，k（0<=k<n）条边是免费的，你所选择的超出k条边的边中最大边权就是你的话费。问最小花费是多少。

解题报告：

方法1：

二分枚举花费，小于等于这个花费的边权赋值为0，否则赋值为1。

求1~n的最短路，如果> k不符合，<=k符合

方法2：

限制条件最短路：二维dij

d[i][j]表示在j号节点用了i次免费的最少花费是多少。

转移：nowi,nowj是当前的状态，to, value是nowi，nowj状态出边的节点和边权。

d[nowi][to] = max(d[nowi][nowj], v al)

d[nowi + 1][to] = d[nowi][nowj])

代码如下（方法2）：

#include<iostream>
#include<queue>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
struct edge{int to, val, next;}e[200001];
int n, p, k, v[1301], d[1301][1301], cnt;
bool vst[1301][1301];
void insert(int from, int to, int val)
{
    e[cnt].to = to, e[cnt].val = val;
    e[cnt].next = v[from]; v[from] = cnt++;
}
struct pint
{
    int a, b, dis;
    pint(int a, int b, int dis):a(a), b(b), dis(dis){}
    friend bool operator < (pint aa, pint bb){return aa.dis > bb.dis;}
};
int main()
{
    while(scanf("%d%d%d", &n, &p, &k) != EOF)
    {
        memset(v, -1, sizeof(int) * (n + 1)); cnt = 0;
        for(int i = 0; i < p; i++)
        {
            int a, b, c;scanf("%d%d%d", &a, &b, &c);
            insert(a, b, c), insert(b, a, c);
        }
        priority_queue<pint> heap;
        for(int i = 0; i <= k; i++) for(int j = 0; j <= n; j++)
            d[i][j] = 0x7fffffff, vst[i][j] = 0;
        heap.push(pint(0, 1, 0));d[0][1] = 0;
        int ans = -1;
        while(!heap.empty())
        {
            pint tmp = heap.top(); heap.pop();
            if (tmp.b == n)
            {
                if (ans == -1 || d[tmp.a][tmp.b] < ans) ans = d[tmp.a][tmp.b];
            }
            if (vst[tmp.a][tmp.b]) continue;
            vst[tmp.a][tmp.b] = 1;
            for(int i = v[tmp.b]; i != -1; i = e[i].next)
            {
                if (max(d[tmp.a][tmp.b], e[i].val) < d[tmp.a][e[i].to])
                    d[tmp.a][e[i].to] = max(d[tmp.a][tmp.b], e[i].val), heap.push(pint(tmp.a, e[i].to, d[tmp.a][e[i].to]));
                if (tmp.a + 1 <= k && d[tmp.a][tmp.b] < d[tmp.a + 1][e[i].to])
                    d[tmp.a + 1][e[i].to] = d[tmp.a][tmp.b], heap.push(pint(tmp.a + 1, e[i].to, d[tmp.a + 1][e[i].to]));
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}