toj_2870.cpp

来自「Tianjin University Online Judge 的80多道题目 」· C++ 代码 · 共 50 行

/*/*
ID: trulo_11
PROG:
LANG: C++
*/
#include<stdio.h>
#define F(i,a,n)for(int i=a;i<n;++i)
#define pii pair<int,int>
#include<algorithm>
#include<vector>
#include<deque>
#include<map>
#include<set>
#include<fstream>
#include<string>
#include<sstream>
#include<iostream>
#include<string.h>
#include<ctype.h>
#include<math.h>
#include<queue>
#define oo 1000000000
#define all(v) (v).begin(),(v).end()
#define Fe(it,v)for(__typeof__((v).begin()) it=(v).begin();it!=(v).end();++it)
using namespace std;
int main(){
  int n,m;
  int f[200][200];
  while(scanf("%d",&n)==1&&n){
    F(i,0,n)F(j,0,n)f[i][j]=oo;
    F(i,0,n)f[i][i]=0;
    scanf("%d",&m);
    F(i,0,m){
      int a,b,c;
      scanf("%d%d%d",&a,&b,&c);
      f[a][b]=f[b][a]=c;
    }
    F(k,0,n)F(i,0,n)F(j,0,n){
      int t=f[i][k]+f[k][j];
      if(t<f[i][j])f[i][j]=t;
    }
    pii a[200];
    F(i,0,n)a[i]=pii(f[0][i],i);
    sort(a,a+n);
    int k;
    scanf("%d",&k);
    printf("%d\n",a[k].second);
  }
}