题解
一看就知道是二分答案的类型。
二分最小费用$x$，然后看路上最少经过几条费用比他多的路。
这题就一个地方有点绕：怎么求$1$-$n$之间路上有几条这样的路？
要么边跑最短路边特判，要么把边分类，
大于$x$的边权设$1$，小于的设$0$。
这样就解决了这道题。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
using namespace std;
typedef long long ll;
struct Edge{
int v,cost,_next;
};
Edge edge[20005],_edge[20005];
int V,E,K,at[1005],cnt=0,maxi=0;
int d[1005],que[50005],f,r,in[1005]={0};
void addedge(int _u,int _v,int _c){
edge[cnt].v=_v,
edge[cnt].cost=_c,
edge[cnt]._next=at[_u],
at[_u]=cnt++;
}
void spfa_bfs(int S){
fill(d,d+V,INF);
d[S]=0;
f=r=0,que[r++]=S,in[S]=1;
while(r-f){
int h=que[f++],_v,_c;
for(int i=at[h];i!=-1;i=_edge[i]._next){
_v=_edge[i].v,_c=_edge[i].cost;
if(d[_v]>d[h]+_c){
d[_v]=d[h]+_c;
if(!in[_v])
in[_v]=1,que[r++]=_v;
}
}
in[h]=0;
}
}
void init(){
scanf("%d%d%d",&V,&E,&K);
memset(at,-1,sizeof(at));
int u,v,c;
for(int i=0;i<E;i++)
scanf("%d%d%d",&u,&v,&c),
addedge(u-1,v-1,c),
addedge(v-1,u-1,c),
maxi=max(maxi,c);
}
void solve(){
int L=0,R=maxi,M;
memcpy(_edge,edge,sizeof(edge));
while(R-L){
int M=(R+L)/2;
for(int i=0;i<cnt;i++)
_edge[i].cost=(edge[i].cost>M);
spfa_bfs(0);
if(d[V-1]==INF){
printf("-1\n");
return ;
}
if(d[V-1]>K)L=M+1;
else R=M;
}
printf("%d\n",L);
}
int main(){
init();
solve();
return 0;
}