题意：
一个无向带权图，要求将第1个节点与第n个节点联通，求路径中第p+1长边。如果p>n，输出0；如果不可能联通，输出-1
解法：
我的做法很搓。。二分+dij最短路，邻接矩阵实现。复杂度高达10^7。。如果哪位神牛有更好的方法，请留言或者E-mail告诉我，谢谢
具体做法如下：二分第p+1边长度len，然后将图的权值重置：如果g[i][j]<=len，则g[i][j]=0,否则g[i][j]=1。然后用dji求最短路。。如果1到n距离小于等于p，则返回true。
代码：
1 # include <cstdio>
2 # include <vector>
3 # include <algorithm>
4 # include <queue>
5 # include <cstring>
6 using namespace std;
7 int n,p,k;
8 vector<int>len;
9 int g[1001][1001];
10 int used[1001];
11 bool visited[1001];
12 void dfs(int pos)
13 {
14 if(used[pos]) return;
15 used[pos]=true;
16 for(int i=1;i<=n;i++)
17 if(g[pos][i]!=-1)
18 dfs(i);
19 }
20 bool chk(int l)
21 {
22 memset(used,-1,sizeof(used));
23 memset(visited,0,sizeof(visited));
24 used[1]=0;
25 while(true)
26 {
27 int pos=-1,minnum=0xfffffff;
28 for(int i=1;i<=n;i++)
29 if(!visited[i]&&used[i]!=-1&&used[i]<minnum)
30 minnum=used[i],pos=i;
31 if(pos==-1) break;
32 visited[pos]=1;
33 for(int i=1;i<=n;i++)
34 if(!visited[i]&&g[pos][i]!=-1&&(used[i]==-1||used[pos]+(g[pos][i]>l)<used[i]))
35 used[i]=used[pos]+(g[pos][i]>l);
36 }
37 return used[n]<=k;
38 }
39 int main() {
40 scanf("%d%d%d",&n,&p,&k);
41 memset(g,-1,sizeof(g));
42 while(p--)
43 {
44 int a,b,value;
45 scanf("%d%d%d",&a,&b,&value);
46 if(g[a][b]==-1||g[a][b]>value)
47 g[a][b]=g[b][a]=value;
48 len.push_back(value);
49 }
50 sort(len.begin(),len.end());
51 memset(used,0,sizeof(used));
52 dfs(1);
53 if(!used[n]) printf("-1\n");
54 else
55 {
56 int s=0,e=len.size()-1;
57 while(s<=e)
58 {
59 int mid=(s+e)>>1;
60 if(chk(len[mid])) e=mid-1;
61 else s=mid+1;
62 }
63 if(e==-1) printf("0\n");
64 else printf("%d\n",len[e+1]);
65 }
66 return 0;
67 }
68