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;
}