【POJ】1502 MPI Maelstrom

题意：一个处理器给n-1个处理器发送广播，问最短时间。广播时并发，也就是各个路径就大的一方。输入如果是x的话说明两个处理器不能相互通信。输入是矩阵的左三角。

题解：一个最短路的裸题吧。输入的时候注意一下字符的转换。floyd爆一遍之后再对每个路径找最大值即可。

代码：

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 using namespace std;

 const int N=;

 const int inf = 1e9;

 char s[];

 int n;

 int mp[N][N];

 void init(){

     for(int i =  ; i <=  n ;i++){

         for(int j = ; j <= n ;j++){

             if(i == j){

                 mp[i][j] = ;

             }

             else{

                 mp[i][j] = inf;

             }

         }

     }

 }

 void floyd(){

     for(int k = ; k <= n ; k++){

         for(int i = ; i <= n ;i++){

             for(int j = ; j <= n ;j++){

                 mp[i][j] = min(mp[i][j],mp[i][k] + mp[k][j]);

             }

         }

     }

     int ans = -inf;

     for(int i = ; i <= n ;i++){

         if(mp[][i] != inf){

             ans = max(ans,mp[][i]);

         }

     }

     cout<<ans<<endl;

 }

 int main(){

     cin>>n;

     init();

     for(int i = ; i <= n ;i++){

         for(int j = ; j < i; j++){

             cin>>s;

             if(s[]!= 'x'){

                 int num = atoi(s);

                 mp[i][j] = mp[j][i] = num;

             }

         }

     }

     floyd();

     return ;

 }

巴特西

【POJ】1502 MPI Maelstrom

最新文章

热门文章