释疑：
- 一个人可以同时给几个人发送消息
- 结束状态必须是所有人都受到了消息

思路：
1. 通过Stockbrokers(SB？）i发消息，所有人同时收到所花时间 （可以是无穷哦~）
2. 找出第一步所得结果中的值最小的那一个
3. 如果第二步所得结果为无穷，说明此图不可联通~

提示，题中数字均从1开始，如果程序中从0开始，需要相应地改计算公式，以及输出~

欢迎发邮件一起讨论~

源代码着色版：http://ideone.com/a32yM

#include <stdio.h>
int nb=0;
int sp[100][100][101]; // i j k
int min(int a, int b){ if(a<=b) return a; return b; }
int i, j, k;
 
void output(void){
 
        int start_point = 0, time_cost = 9999;
        for(i=0; i<nb; i++){
                int max_value = 0;      
                for( j=0; j<nb; j++ ){
                        if( j!=i && max_value < sp[i][j][nb] ){ max_value=sp[i][j][nb]; }
                }
                if( time_cost > max_value ) {
                        time_cost = max_value; start_point = i;
                }
        }       
        if( time_cost >= 9999 ){ printf("distinct\n"); }
        printf("%d %d\n", start_point+1, time_cost);
}
void cal(void){
        for(k=1; k<nb+1; k++){
                for(i=0; i<nb; i++){
                        for(j=0; j<nb; j++){
                                sp[i][j][k] = min(sp[i][j][k-1], sp[i][k-1][k-1]+sp[k-1][j][k-1]);
                                //printf("%d ", sp[i][j][k]);
                        }//printf("\n");
                }//printf("\n\n");
        }
}
void read_data(void){
        for(i=0; i<nb; i++){
                int t=0;
                scanf("%d", &t);
                for(j=0; j<t; j++){
                        int to=0;
                        scanf("%d", &to);
                        scanf("%d", &(sp[i][to-1][0]) );        
                }
        }       
}
void init(void){
        for(i=0; i<nb; i++){
                for(j=0; j<nb; j++){
                        sp[i][j][0] = 9999;
                }
        }
}
int main(void) {
        while(1){
                scanf("%d", &nb);
                if( nb == 0 ) break;
                init();
                read_data();
                cal();
                output();
        }
        return 0;
}

• Re:题解 (2238) shh 2012-03-25 17:06:03
  • ugg pas cher (1093) Unpanvary 2012-12-01 01:16:45
  • http://www.bootsspaschersoldes.info uggs pas cher (1155) Unpanvary 2012-12-11 15:18:25
• Re:题解 (2222) mxcbetter 2012-11-14 23:07:08