题意:出于竞争目的,股票经纪人要在他们的人际关系网中传播一些谣言。但是每个股票经纪人只能传他给他所熟悉的几个人。当谣言从第一个人传出后,最快经过多多长时间最后一个人可以收到谣言。
题解:通过Floyd求出任意两个人之间的cost。然后分析一下即可。
#include <iostream> using namespace std; #define INF 200000000 int contract[101][101], n; void Floyd () { int i,j,k; for ( k = 1; k <= n; k++ ) { for ( i = 1; i <= n; i++ ) for ( j = 1; j <= n; j++ ) if ( contract[i][j] > contract[i][k] + contract[k][j] ) contract[i][j] = contract[i][k] + contract[k][j]; } } int main() { int i, j, k, t; while ( cin >> n && n ) { for ( i = 1; i <= n; i++ ) for ( j = 1; j <= n; j++ ) contract[i][j] = ( i == j ? 0 : INF ); for ( i = 1; i <= n; i++ ) { cin >> k; for ( j = 1; j <= k; j++ ) { cin >> t; cin >> contract[i][t]; } } Floyd (); int start = -1, temp, time = INF; for ( i = 1; i <= n; i++ ) { temp = 0; for ( j = 1; j <= n; j++ ) { if ( contract[i][j] == INF ) break; if ( contract[i][j] > temp ) temp = contract[i][j]; } if ( temp < time && j == n+1 ) { time = temp; start = i; } } if ( start == -1 ) cout << "disjoint" << endl; else cout << start << ' ' << time << endl; } return 0; }