1376：信使(msner)

【解题思路】
        每个哨所是一个顶点，哨所与哨所之间的通信线路为边，两哨所间通讯花费的时间为边的权值。记第一个哨所为顶点s，信息从第一个哨所传递到表示为顶点x的某哨所可能有多条路径，每条传送路径有一个花费的时间，自然要选择花费时间最少的传送方案，也就是图中从顶点s到顶点x的最短路径。
       从哨所s到哨所x的送信时间就是顶点s到顶点x的最短路径的长度。先求出顶点s到图中其他每个顶点的最短路径。
       要想完成整个送信过程，就要让所有其他哨所都接收到第一个哨所传出的信，完成整个送信过程的时间就是最晚收到信的哨所的收信时间，也就是顶点s到其它所有顶点的最短路径中路径长度最大值。
      该题n最大为100，可以选择使用Floyd算法，Dijkstra算法

【参考代码】

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
int f[102][102];
int n,m;
int main()
{
	memset(f,INF,sizeof(f));
	int x,y,z;
	cin>>n>>m;
	for(int i=1;i<=n;i++) f[i][i]=0;
	for(int i=1;i<=m;i++){
		cin>>x>>y>>z;
		f[x][y]=f[y][x]=z;
	}
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++){
				if((i!=k)&&(j!=k)&&(i!=j)&&(f[i][k]+f[k][j]<f[i][j]))
					f[i][j]=f[i][k]+f[k][j];
			}
	int s=0;
	for(int i=1;i<=n;i++) 
	{
		if(f[1][i]==INF) 
		{
			cout<<-1;
			return 0;
		}
		if(s<f[1][i]) s=f[1][i];
	}
	cout<<s<<endl;
    return 0;
}