4. 第 k 短路径re求条

[陈麟轩]

#include<bits/stdc++.h>
using namespace std;
#define int long long
int x[200005],y[200005],w[200005],num[1005],dist[1005][1005],id[200005];
vector<int> p;
signed main(){
  int n,m,k;
  cin>>n>>m>>k;
  for(int i=0;i<m;i++){
    cin>>x[i]>>y[i]>>w[i];
    x[i]--;y[i]--;
  }
  vector<pair<int,int>>e;
  for(int i=0;i<m;i++)e.push_back({w[i],i});
  sort(e.begin(),e.end());
  int cnt=0;
  for(int i=0;i<min(k,m);++i){
    int idx=e[i].second;
    num[cnt++]=x[idx];
    num[cnt++]=y[idx];
  }
  sort(num,num+cnt);
  cnt=unique(num,num+cnt)-num;
  for(int i=0;i<cnt;++i)id[num[i]]=1;
  for(int i=0;i<cnt;++i){
    for(int j=0;j<cnt;++j){
      dist[i][j]=(i==j)?0:LLONG_MAX/2;
    }
  }
  for(int i=0;i<min(k,m);++i){
    int idx=e[i].second;
    int u=id[x[idx]],v=id[y[idx]];
    dist[u][v]=min(dist[u][v],w[idx]);
    dist[v][u]=min(dist[v][u],w[idx]);
  }
  for(int mid=0;mid<cnt;++mid){
    for(int i=0;i<cnt;++i){
      for(int j=0;j<cnt;++j){
        dist[i][j]=min(dist[i][j],dist[i][mid]+dist[mid][j]);
      }
    }
  }
  for(int i=0;i<cnt;++i){
    for(int j=i+1;j<cnt;++j){
      if(dist[i][j]<LLONG_MAX/2)p.push_back(dist[i][j]);
    }
  }
  sort(p.begin(),p.end());
  cout<<p[k-1];
}

不知道为什么！

[向着星辰与深渊 (原神)]

题目？？？