distinct ...

> 释疑：
> - 一个人可以同时给几个人发送消息
> - 结束状态必须是所有人都受到了消息
> 
> 思路：
> 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;
> }

• 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