K-th Path CodeForces

题目链接：https://vjudge.net/problem/CodeForces-1196F

题意：从图中找出第K短的最短路，最短路：从一个点到另一个的最短距离。

思路：题目说了，每两个点之间的边小于等于1，那么如果我们只取K条边，

那么顶点数 V∈[K,2K]，所以我们一定可以在K条边中的到第K短的最短路。

当然我们先要把所有变来一个sort，取权值小的K条边。

之后跑一个floyd就可以了，然后把所有最短路存下来，找出第K小的最短路。

ps（这里的编号很方便，我是参考另一个大佬的，这里说明一下，当然也可以和我之前一样，

来个计数的慢慢编号）。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <queue>

 #include <map>

 #include <cmath>

 #include <iomanip>

 using namespace std;

 typedef long long LL;

 #define inf (1LL << 60)

 #define rep(i,j,k) for(int i = (j); i <= (k); i++)

 #define rep__(i,j,k) for(int i = (j); i < (k); i++)

 #define per(i,j,k) for(int i = (j); i >= (k); i--)

 #define per__(i,j,k) for(int i = (j); i > (k); i--)

 const int N = (int)2e5 + ;

 LL tmp[N];

 LL dis[][];

 int n,m,k;

 map<int, int> s;

 int tot;

 struct node{

     int u;

     int v;

     int w;

     bool friend operator < (node a,node b){

         return a.w < b.w;

     }

 }o[N];    

 int ID(int x){

     if(s.count(x)) return s[x];

     return s[x] = ++tot;

 }

 int main(){

     ios::sync_with_stdio(false);

     cin.tie();

     cin >> n >> m >> k;

     int u,v,w,l = ;

     //存边

     rep(i,,m){

         cin >> u >> v >> w;

         o[l].u = u;

         o[l].v = v;

         o[l++].w = w;

     }

     //sort边，取前K条

     sort(o,o + m);

     rep(i,,) rep(j,,){

         if(i == j) dis[i][j] = ;

         else dis[i][j] = inf;

     }

     //建图

     rep__(i,,min(m,k)){

         dis[ID(o[i].u)][ID(o[i].v)] = dis[ID(o[i].v)][ID(o[i].u)] = o[i].w;

     }

     rep(k,,tot) rep(i,,tot) rep(j,,tot){

         dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);

     }

     l = ;

     rep(i,,tot) rep(j,i + ,tot){

         tmp[l++] = dis[i][j];

     }

     sort(tmp, tmp + l);

     cout << tmp[k - ] << endl;

     getchar();getchar();

     return ;

 }

巴特西

K-th Path CodeForces - 1196F

最新文章

热门文章