记录编号	98366	评测结果	AAAAAAAA
题目名称	服务点设置	最终得分	100
用户昵称	FF_Sky||幻	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2014-04-22 19:58:25	内存使用	0.57 MiB

#include <cstdio>
#include <cstring>
#define INF 0x3f3f3f3f
#define N 100
#define M 21000
using namespace std;
 
int w[N][N],ver[M],next[M],head[M],h[N],d[N],c[N],n,m,tot,p;
 
void swap(int &x,int &y){
	if (x == y) return;
	x = x^y;
	y = x^y;
	x = x^y;
}
 
void add(int x,int y,int z){
	ver[++tot] = y; next[tot] = head[x]; head[x] = tot;
	ver[++tot] = x; next[tot] = head[y]; head[y] = tot;
}
 
void up(int i){
	for (int pp = i>>1; pp; pp = i>>1){
		if (d[h[i]] < d[h[pp]]){
			swap(c[h[i]],c[h[pp]]);
			swap(h[i],h[pp]);
		}
		else return;
		i = pp;
	}
}
 
void down(int i){
	for (int pp = i<<1; pp <= p; pp = i<<1){
		if (d[h[pp+1]] < d[h[pp]] && pp < p) pp++;
		if (d[h[pp]] < d[h[i]]){
			swap(c[h[i]],c[h[pp]]);
			swap(h[i],h[pp]);
		}
		else return;
		i = pp;
	}
}
 
void dijis(int st){
	int x,j;
	p = 1;
	memset(d,INF,sizeof(d));
	memset(c,0,sizeof(c));
	d[st] = 0;
	h[p] = st;
	while (p){
		x = h[1];
		c[x] = 0; c[h[p]] = 1;
		h[1] = h[p--];
		down(1);
		for (j = head[x]; j; j = next[j]){
			if (d[ver[j]] > d[x]+w[x][ver[j]]){
				d[ver[j]] = d[x]+w[x][ver[j]];
				if (!c[ver[j]]){
					h[++p] = ver[j];
					c[ver[j]] = p;
					up(p);
				}
				else up(c[ver[j]]);
			}
		}
	}
}
 
int main(){
	freopen("djsa.in","r",stdin);
	freopen("djsa.out","w",stdout);
	int i,j,k,temp,x,y,z,minans;
	scanf("%d%d",&n,&m);
	for (i = 1; i <= m; i++){
		scanf("%d%d%d",&x,&y,&z);
		if (!w[x][y]){
			add(x,y,z);
			w[x][y] = z;
			w[y][x] = z;
		}
		else{
			w[x][y] = z;
			w[y][x] = z;
		}
	}
	minans = INF;
	for (i = 0; i < n; i++){
		dijis(i);
		temp = 0;
		for (j = 0; j < n; j++)
			if (d[j] > temp) temp = d[j];
		if (temp < minans) minans = temp,k = i;
	}
	printf("%d",k);
	return 0;
}