poj 1125 Stockbroker Grapevine 【最短路 Floyd】

客官°小女子只卖身不卖艺 2022-08-09 15:56 136阅读 0赞

Stockbroker Grapevine

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong> 1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong> 10000K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong> 31794</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong> 17420</td> 
  </tr> 
 </tbody> 
</table>

题目大意：给你n个人的联系情况，对任意一个人，求出这个人发消息到其他n-1个人的时间，得到n-1个时间中的最大值，n个最大值中的最小值就是所求。如果网络不通，那就输出disjoint。

本题用Floyd更简洁

已Accept代码【c++】

<table width="100%" class="a" bordercolor="#ffffff" border="1" cellspacing="0" cellpadding="0"><tbody><tr align="center"><td><a target=_blank href="http://poj.org/problem?id=1125"><span style="color:#0000ff;">1125</span></a></td><td><span style="color:blue;">Accepted</span></td><td>140K</td><td>0MS</td><td>C++</td><td>923B</td></tr></tbody></table>

#include <cstdio>
    #include <cstring>
    using namespace std;
    int map[101][101];
    int n, m;
    
    void Floyd() {
    	int v = 0;
    	for(int k = 1; k <= n; k++)
    		for(int i = 1; i <= n; i++)
    			for(int j = 1; j <= n; j++)
    				map[i][j] = map[i][j] > map[i][k] +map[k][j] ? map[i][k] + map[k][j] : map[i][j];
    	int Min = 100000;
    	for(int i = 1; i <= n; i++) {
    		int Max = -1;
    		for(int j = 1; j <= n; j++)
    			if(Max < map[i][j])
    				Max = map[i][j];
    		if(Max < Min) {
    			Min = Max;
    			v = i;
    		}
    	}	
    	if(Min < 100000)
    		printf("%d %d\n", v, Min);
    	else
    		printf("disjoint\n");
    }
    
    int main() {
    	int a, b;
    	while(scanf("%d", &n), n) {
    		for(int i = 1; i <= n; i++) {
    			for(int j = 1; j <= n; j++) {
    				if(i == j)
    					map[i][j] = 0;
    				else
    					map[i][j] = 100000;
    			}
    		}
    		for(int i = 1; i <= n; i++) {
    			scanf("%d", &m);
    			for(int j = 0; j < m; j++) {
    				scanf("%d %d", &a, &b);
    				map[i][a] = b;
    			}
    		}
    		Floyd();
    	}
    	return 0;
    }