codevs原創抄襲題 5960 信使，codevs5960
題目描述 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所能到達的點中，距離最遠的一定是最後的點，這就是最短路徑（因為每個節點最少經過一次）
![]()
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 using namespace std;
5 int map[101][101];
6 int maxn=0xf;
7 int main()
8 {
9 memset(map,maxn,sizeof(map));
10 int n,m;
11 cin>>n>>m;
12 for(int i=1; i<=m; i++)
13 {
14 int x,y,z;
15 scanf("%d%d%d",&x,&y,&z);
16 map[x][y]=map[y][x]=z;
17 }
18 map[1][1]=0;
19 for(int k=1; k<=n; k++)
20 {
21 for(int i=1; i<=n; i++)
22 {
23 for(int j=1; j<=n; j++)
24 {
25 if(map[i][j]>map[i][k]+map[k][j])
26 {
27 map[i][j]=map[i][k]+map[k][j];
28 }
29 }
30 }
31 }
32
33 int ans=-1;
34 for(int i=2;i<=n;i++)
35 {
36 if(map[1][i]>ans)
37 {
38 ans=map[1][i];
39 }
40 else
41 {
42 if(map[1][i]==maxn)
43 {
44 cout<<-1;
45 return 0;
46 }
47 }
48 }
49 cout<<ans;
50 return 0;
51 }
View Code
