3. 服务点设置
★ 输入文件：djsa.in 输出文件：djsa.out 简单对比
时间限制：1 s 内存限制：128 MB
【问题描述】
为了进一步普及九年义务教育，政府要在某乡镇建立一所希望小学，该乡镇共有n个村庄，村庄间的距离已知，请问学校建在哪个村庄最好？（好坏的标准是学生就近入学，即在来上学的学生中，以最远的学生走的路程为标准。或者说最远的学生与学校的距离尽可能的小。）
【输入格式】
输入由若干行组成，第一行有两个整数，n（1≤n≤100）、m（1≤m≤n*n）；n表示村庄数，m表示村庄间道路数。第2至m+1行是每条路的信息，每行三个整数，为道路的起点、终点和两村庄间距离。（村庄从0开始编号）
【输出格式】
一个整数，学校所在村庄编号(如果两个村庄都适合建立学校，选择编号小的村庄建学校)。
【样例输入】
6 8
0 2 10
0 4 30
0 5 100
1 2 5
2 3 50
3 5 10
4 3 20
4 5 60
【样例输出】
4 QAQ太蒟了 我又来水题了
这一道题看起来非常简单的样子 100个点 10000条边 。。。。。
以每一个点为起点跑一遍dijkstra
再On地在dis数组中取一下最大值（这是+的，可忽略不计） 时间复杂度？声明：本人这是无脑暴力QAQ n*(n+m*logm +n)
100*(100+10000*14+100) 如果有不对的地方敬请指正（平常也不大算）
1400 0000 ？应该能跑过（况且数据不会那么极限嘛QAQ） 那我们就来暴力一遍吧（自认为是暴力的做法 但也想不出更好的做法 啊）
天呐我也是绝望了 第七个点究竟是怎么WA的 QAQ 数据毒瘤
//WA一个点的超弱代码
#include<bits/stdc++.h>
#define pa pair<int,int>
#define maxn 105
#define INF 0x3f3f3f3f
using namespace std;
int n,m;
vector<int> v[maxn],w[maxn];
int dis[maxn],vis[maxn];
priority_queue<pa,vector<pa>,greater<pa> > q;
void Dijkstra(int S)//模板一顿猛敲
{
memset(dis,0x3f,sizeof(dis));
memset(vis,,sizeof(vis));
dis[S]=;
//那个队列不用单独再从头到尾清空 因为每跑完一遍Dijkstra 队列就弹空了
q.push(make_pair(,S));
while(!q.empty())
{
int x=q.top().second;
q.pop();
if(vis[x]) continue;
vis[x]=;
for(int i=;i<v[x].size();i++)
{
int y=v[x][i];
int val=w[x][i];
if(dis[y]>dis[x]+w[x][i])
{
dis[y]=dis[x]+w[x][i];
q.push(make_pair(dis[y],y));
}
}
}
}
bool BianBuild[maxn][maxn];
int main()
{
freopen("djsa.in","r",stdin);
freopen("djsa.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
int x,y,z;scanf("%d%d%d",&x,&y,&z);
if(BianBuild[x][y])//天呐 这一道题的数据居然有重边!QAQ 边权要取一个较大的
{
int Index_inx,Index_iny;
for(int j=;j<v[x].size();j++)
if(v[x][j]==y)
{
Index_inx=j;
break;
}
for(int j=;j<v[y].size();j++)
if(v[y][j]==x)
{
Index_iny=j;
break;
}
w[x][Index_inx]=max(w[x][Index_inx],z);
w[y][Index_iny]=max(w[y][Index_iny],z);
continue;
}
BianBuild[x][y]=BianBuild[y][x]=true;
v[x].push_back(y);v[y].push_back(x);
w[x].push_back(z);w[y].push_back(z);//QAQ这好像是双向边诶 天呐
}
int mi=INF,miIndex=;
for(int i=;i<n;i++)//标号从0开始
{
Dijkstra(i);
int mx=-INF;
for(int j=;j<n;j++)
mx=max(mx,dis[j]);
if(mx<mi)
{
mi=mx;
miIndex=i;
}
}
printf("%d",miIndex);
return ;
}