Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:题解

Posted by mxcbetter at 2012-11-14 23:07:08 on Problem 1125
In Reply To:题解 Posted by:jwzxgo at 2012-03-10 03:33:50
> 释疑:
> - 一个人可以同时给几个人发送消息
> - 结束状态必须是所有人都受到了消息
> 
> 思路:
> 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;
> }

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator