1196F - K-th Path

题目链接：

http://codeforces.com/problemset/problem/1196/F

题目大意：：无向图，求任意两点第k短的路径

思路:按照边的大小，只保留前K个边，如果不连同的话， 第K小的边一定是这K个边中的一个，连同的话，一定是这K个边之间的复合边。重新编号，然后跑floyd。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1E18+7;
const int N=2E5+7;
struct stu{
    ll a,b,c;
    bool friend  operator < (const stu &x,const stu &y){
        return x.c>y.c;
    }
};
priority_queue<stu >que;
vector<ll >v;
vector<stu >ve[N];
ll mark[N];
ll dp[800+7][800+7];
int main(){
    ll n,m,k;
    cin>>n>>m>>k;
    ll x,y,z;
    for(int i=1;i<=m;i++){
        cin>>x>>y>>z;
        que.push({x,y,z});
    }
    ll pos=1;
    int s=k*2;
    for(int i=1;i<=s;i++){
        for(int j=1;j<=s;j++){
            dp[i][j]=INF;
        }
    }
    for(int i=1;i<=s;i++) dp[i][i]=0;
    for(int i=1;i<=k&&!que.empty();i++){
        stu x1=que.top();
        que.pop();
        int da=x1.a;
        int db=x1.b;
        if(mark[da]){
            da=mark[da];
        }
        else {
            mark[da]=pos++;
            da=mark[da];
        }
        if(mark[db]) db=mark[db];
        else {
            mark[db]=pos++;
            db=mark[db];
        }
        dp[da][db]=x1.c;
        dp[db][da]=x1.c;
    }

    for(int i=1;i<pos;i++){
        for(int j=1;j<pos;j++){
            for(int k=1;k<pos;k++){
                dp[j][k]=min(dp[j][k],dp[j][i]+dp[i][k]);
            }
        }
    }
    for(int i=1;i<pos;i++){
        for(int j=i+1;j<pos;j++){
            v.push_back(dp[i][j]);
        }
    }
    sort(v.begin(),v.end());
    cout<<v[k-1]<<endl;
    return 0;
}