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

Accept代码!理解了就超简单!

Posted by slow at 2011-01-11 11:56:13 on Problem 1797
#include <iostream>
#include<cmath>
#include<cstring>
#include<stdlib.h>
#include<stdio.h>
using namespace std;
#define MAX 0x7fffffff
#define Min(a, b) ((a) < (b) ? (a) : (b))    
int map[1010][1010],dis[1010];
int mark[1010];
int n,m,s,t,W=0;
void Dijkstra()
{
       int i , j , k , min ;
       for( i = 1 ; i <= n ; i++ )   
       {
              mark[i] = 0 ; 
              if(map[1][i]!=0)  
              dis[i] = map[1][i] ;
              else
              dis[i]=MAX;   
       }
       mark[1] = 1 ;
       for( i = 1 ; i < n ; i++ )   
       {
              min = 0; 
              for( j = 1 ; j <= n ; j++ )
                     if(!mark[j] && dis[j] > min&&dis[j]!=MAX)
                     {
                            min = dis[j];
                            k = j ;   
                     }
              mark[k] = 1;   
              for( j = 1 ; j <= n ; j++ )     
                     if(!mark[j] )
                     {  
                        int Q;
                        Q=Min(dis[k],map[k][j]);                         
                        if(dis[j]<Q&&map[k][j]!=0)
                        {                                             
                         dis[j] = Q; 
                        }   
                     }
       }
              printf("Scenario #%d:\n%d\n\n",W,dis[n]);      
}
int main()
{
       int i , j , x , y , d,N ;
       scanf("%d",&N);
       while(N--)
       {
              scanf("%d %d",&n,&m);
              W++;         
              memset(map,0,sizeof(map));
       
              for( i = 1 ; i <= m ; i++ ) 
              {
                     scanf("%d %d %d",&x,&y,&d);
                     map[x][y] = map[y][x] = d ;
              }
              Dijkstra(); 
       }
       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