发现到 $K$ 不大，考虑有什么和 $K$ 有关的结论
发现答案似乎只会经过前 $K$ 小的边，如果边权第 $K$ 小的边有多条那么可以任意取
证明挺显然的吧，首先如果走了边权排名大于 $K$ 的边那么总的排名也一定大于 $K$，并且如果经过第 $K$ 名的边那么我们就只要考虑只走这一条边的路径，不然总路径排名也一定大于 $K$
那么对于第 $K$ 名的边我们不用考虑它对图的贡献，任取即可
然后把有用的边和点拿出来离散化一下，那么总点数小于等于 $800$ ，直接 $floyd$ 然后对所有路径排序即可
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=1007,M=2e5+7; int n,m,K; struct edge { int u,v,w; edge (int _u=0,int _v=0,int _w=0) { u=_u,v=_v,w=_w; } inline bool operator < (const edge &tmp) const { return w<tmp.w; } }E[M]; int d[N]; ll dis[N][N],D[N]; int main() { n=read(),m=read(),K=read(); int a,b,c; for(int i=1;i<=m;i++) { a=read(),b=read(),c=read(); E[i]=edge(a,b,c); } sort(E+1,E+m+1); int tot=0; for(int i=1;i<=min(m,K);i++) d[++tot]=E[i].u,d[++tot]=E[i].v; sort(d+1,d+tot+1); tot=unique(d+1,d+tot+1)-d-1; memset(dis,0x3f,sizeof(dis)); for(int i=1;i<=tot;i++) dis[i][i]=0; for(int i=1;i<=min(m,K);i++) { int x=lower_bound(d+1,d+tot+1,E[i].u)-d; int y=lower_bound(d+1,d+tot+1,E[i].v)-d; dis[x][y]=dis[y][x]=E[i].w; } for(int k=1;k<=tot;k++) for(int i=1;i<=tot;i++) for(int j=1;j<=tot;j++) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); int cnt=0; for(int i=1;i<=tot;i++) for(int j=i+1;j<=tot;j++) D[++cnt]=dis[i][j]; sort(D+1,D+cnt+1); printf("%lld\n",D[K]); return 0; }