題意：
一個無向帶權(quán)圖，要求將第1個節(jié)點(diǎn)與第n個節(jié)點(diǎn)聯(lián)通，求路徑中第p+1長邊。如果p>n，輸出0；如果不可能聯(lián)通，輸出-1
解法：
我的做法很搓。。二分+dij最短路，鄰接矩陣實(shí)現(xiàn)。復(fù)雜度高達(dá)10^7。。如果哪位神牛有更好的方法，請留言或者E-mail告訴我，謝謝
具體做法如下：二分第p+1邊長度len，然后將圖的權(quán)值重置：如果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