K-th Path Codeforces Round #575 (Div. 3)

45 阅读 0 评论 30 点赞

我是靠谱客的博主激情店员，最近开发中收集的这篇文章主要介绍K-th Path Codeforces Round #575 (Div. 3)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

链接: https://codeforces.com/contest/1196/problem/F
题面:
You need to print the k-th smallest shortest path in this graph (paths from the vertex to itself are not counted, paths from i to j and from j to i are counted as one).

More formally, if d is the matrix of shortest paths, where di,j is the length of the shortest path between vertices i and j (1≤i<j≤n), then you need to print the k-th element in the sorted array consisting of all di,j, where 1≤i<j≤n.，k<=400,2≤m,n≤2e5
题意: 给你一个无向图，求出图中任意两点距离排在第K短的距离
思路: 一开始觉得这道题很难，2e5个点，想着怎么跑全图得答案，但有没有发现k最大只有400，所以我们可以想第k条小的边是不是答案呢？答案显而易见没那么简单，所以我们可以把前k条边扣出来重构一个图，跑一遍floy然后将所有距离进行排序，这时候第K小的距离就是所求的答案，所以这道题的稍微难的点就是在重构图上，我们可以将前k条边的点存起来，将点进行离散化后，将数据储存在矩阵中，图重构就完成了，全图跑一遍floy求最短路就行了

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=2e5+5;
struct node
{
int u,v,w;
friend bool operator <(const node &a,const node &b)
{
return a.w<b.w;
}
}edge[N];
ll mp[805][805];
int b[805];
ll dis[N];
int main()
{
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
}
sort(edge+1,edge+1+m);
int cnt=0;
for(int i=1;i<=min(k,m);i++)
{
b[++cnt]=edge[i].u;
b[++cnt]=edge[i].v;
}
sort(b+1,b+1+cnt);
cnt=unique(b+1,b+1+cnt)-b-1;
for(int i=1;i<=cnt;i++)
for(int j=1;j<=cnt;j++)
{
mp[i][j]=(1ll<<60);
}
for(int i=1;i<=min(k,m);i++)
{
int u=lower_bound(b+1,b+1+cnt,edge[i].u)-b;
int v=lower_bound(b+1,b+1+cnt,edge[i].v)-b;
//cout<<u<<' '<<v<<endl;
mp[u][v]=mp[v][u]=edge[i].w;
}
for(int k=1;k<=cnt;k++)
{
for(int i=1;i<=cnt;i++)
{
for(int j=1;j<=cnt;j++)
{
if(mp[i][j]>mp[i][k]+mp[k][j]){
mp[i][j]=mp[i][k]+mp[k][j];
}
}
}
}
int cnt1=0;
for(int i=1;i<=cnt;i++)
for(int j=i+1;j<=cnt;j++)
{
if(mp[i][j]!=(1ll<<60))
{
dis[++cnt1]=mp[i][j];
}
}
sort(dis+1,dis+1+cnt1);
printf("%lldn",dis[k]);
return 0;
}