【題目描述】

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

現在總指揮請你編一個程序，計算出完成整個送信過程最短需要多少時間。

【輸入】

第1行有兩個整數n和m，中間用1個空格隔開，分別表示有n個哨所和m條通信線路,且1≤n≤100。

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

【輸出】

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

【輸入樣例】

4 4
1 2 4
2 3 7
2 4 1
3 4 6

【輸出樣例】

11

【源程序】

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<string> #include<cstdlib> #include<queue> #include<vector> #include<set> #define INF 0x3f3f3f3f #define PI acos(-1.0) #define N 101 #define MOD 123 #define E 1e-6 using namespace std; int g[N][N]; int main() {int n,m;cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i==j)g[i][j]=0;elseg[i][j]=INF;}}for(int i=1;i<=m;i++){int x,y,w;cin>>x>>y>>w;g[x][y]=w;g[y][x]=w;}for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(g[i][j]>g[i][k]+g[k][j])g[i][j]=g[i][k]+g[k][j];int maxx=-INF;for(int i=1;i<=n;i++)if(g[1][i]>maxx)maxx=g[1][i];if(maxx==INF)cout<<"-1"<<endl;elsecout<<maxx<<endl;return 0; }

?

總結

以上是生活随笔為你收集整理的信使（信息学奥赛一本通-T1376）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。