codevs原創抄襲題 5960 信使

題目描述?Description

??戰爭時期，前線有n個哨所，每個哨所可能會與其他若干個哨所之間有通信聯系。信使負責在哨所之間傳遞信息，當然，這是要花費一定時間的（以天為單位）。指揮部設在第一個哨所。當指揮部下達一個命令后，指揮部就派出若干個信使向與指揮部相連的哨所送信。當一個哨所接到信后，這個哨所內的信使們也以同樣的方式向其他哨所送信。直至所有n個哨所全部接到命令后，送信才算成功。因為準備充足，每個哨所內都安排了足夠的信使（如果一個哨所與其他k個哨所有通信聯系的話，這個哨所內至少會配備k個信使）。??????現在總指揮請你編一個程序，計算出完成整個送信過程最短需要多少時間

輸入描述?Input Description

??第1行有兩個整數n和m，中間用1個空格隔開，分別表示有n個哨所和m條通信線路。1<=n<=100。??????第2至m+1行：每行三個整數i、j、k，中間用1個空格隔開，表示第i個和第j個哨所之間存在通信線路，且這條線路要花費k天。??

輸出描述?Output Description

輸出文件msner.out，僅一個整數，表示完成整個送信過程的最短時間。如果不是所有的哨所都能收到信，就輸出-1。

樣例輸入?Sample Input

??4 4??????

1 2 4??????

2 3 7?????

2 4 1??????

3 4 6??

樣例輸出?Sample Output

11

數據范圍及提示?Data Size & Hint

1<=n<=100

分類標簽?Tags?點此展開?

?

思路：用Floyed求出最短路徑

　　然后枚舉從1-n的節點，取最大值

　　如果還有沒有松弛過得點

　　那么輸出-1

　　原理：如果這個圖滿足條件，那么從1一定可以遍歷完整個圖，那么在1所能到達的點中，距離最遠的一定是最后的點，這就是最短路徑（因為每個節點最少經過一次）

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int map[101][101];
int maxn=0xf;
int main() 
{
    memset(map,maxn,sizeof(map));
    int n,m;
    cin>>n>>m;
    for(int i=1; i<=m; i++) 
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        map[x][y]=map[y][x]=z;
    }
    map[1][1]=0;
    for(int k=1; k<=n; k++) 
    {
        for(int i=1; i<=n; i++) 
        {
            for(int j=1; j<=n; j++) 
            {
                if(map[i][j]>map[i][k]+map[k][j]) 
                {
                    map[i][j]=map[i][k]+map[k][j];
                }
            }
        }
    }
    
    int ans=-1;
    for(int i=2;i<=n;i++)
    {
        if(map[1][i]>ans)
        {
            ans=map[1][i];
        }
        else
        {
            if(map[1][i]==maxn)
            {
                cout<<-1;
                return 0;
            }
        }
    }
    cout<<ans;
    return 0;
}

?