1~n的路径,第K+1大的边权尽可能小
显然二分答案,那么问题的关键变成了在最短路上能否有不超过k个大于val的边
换句话说超过val的值上是否超过k个
对于这种统计个数的问题,可以考虑用01最短路来解决
int dij()
{
q.pb(1); d[1]=0;
while(!q.empty())
{
int x=q.front(); q.pop_front();
vis[x]=1;
for(int i=head[x];i;i=e[i].next)
{
int y=e[i].to,z=e[i].w;
if(d[y]>d[x]+z)
{
d[y]=d[x]+z;
z?q.pb(y):q.pf(y);
}
}
}
return d[n];
}
bool check(int x)
{
clean();
for(int i=1;i<=m;i++) add(s[i].a,s[i].b,s[i].c>x);
int ret=dij();
if(ret==inf){ puts("-1");exit(0);}
return ret<=k;
}
bool cmp(Node x,Node y){return x.c<y.c;}
int find()
{
sort(s+1,s+m+1,cmp);
s[m+1]={0,0,inf}; int l=0,r=m;
while(l+1<r)
{
int mid=(l+r)>>1;
if(check(s[mid].c))r=mid;//如果当前价值满足条件的话 尝试花费更少的钱
else l=mid;
}
return s[r].c;
}
int main()
{
n=read(); m=read(); k=read();
for(int i=1;i<=m;i++)
{
int x=read(),y=read(),z=read();
s[i]={x,y,z};
}
if(check(0)){puts("0");return 0;}
printf("%d",find());
return 0;
}
注意: 一定要在枚举集合内部包括所有可能的答案 尤其是边界情况 例如0或者inf之类的数值