#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;
}

• Re:Accept代码！理解了就超简单！ (1975) 516108736 2015-12-02 17:40:50
• Re:Accept代码！理解了就超简单！ (1975) Sogekinger 2017-10-05 21:15:49
  • Re:Accept代码！理解了就超简单！ (11) 2507409218 2018-05-21 17:55:07
    • Re:Accept代码！理解了就超简单！ (1389) 2507409218 2018-05-21 17:59:03
    • Re:Accept代码！理解了就超简单！ (17) AcTyewece 2018-05-23 20:07:02