HDU 2544 最短路 Dijkstra-白红宇

HDU 2544 最短路 Dijkstra

阅读量：5172 次

发布时间：2019-06-13

本文共 1506 字，大约阅读时间需要 5 分钟。

/*很简单的模版题...Dijkstra应该就不用多说了...算法比较简单...尤其是数据结构中的...所以流程图都有...大家一搜一大堆我就不赘述了...赘述也是多余给几组数据3 31 2 11 3 32 3 13 11 2 16 91 2 71 3 91 4 142 3 102 5 153 4 23 5 114 6 95 6 66 81 3 101 5 301 6 1002 3 53 4 504 6 105 4 205 6 60****************************************************2-1 20 60*/#include 
    
     #include 
     #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      using namespace std;const int INF = 0x3fffffff;const int V = 200;int dijkstra(int map[][V],int start,int end,int n) //map为临界矩阵,n为矩阵大小{ int final[V],track[V],i,j,ant=n*n; memset(track,0,sizeof(track)); for(i=1;i<=n;i++) final[i]=map[start][i]!=0?map[start][i]:INF; track[start]=1; while(ant--) { int judge=1,min=INF,getmin=start; for(i=1;i<=n;i++) judge*=track[i]; if(judge) return final[end]; for(i=1;i<=n;i++) { if( final[i] < min && final[i]!=INF && track[i]==0) { getmin = i; min = final[i]; } final[i] = final[start]+(map[start][i]==0?INF:map[start][i]) < final[i] ? final[start]+(map[start][i]==0?INF:map[start][i]) : final[i]; } track[getmin]=1; start = getmin; } return -1;}int main(){// freopen("in.txt","r",stdin); int i,j,n,m,map[V][V]; while(cin>>n>>m && (n!=0 || m!=0)) { memset(map,0,sizeof(map)); while(m--) { int a,b,c; cin>>a>>b>>c; if(map[a][b]!=0) { map[a][b] = c
                      
                       >start>>end; cout<
                       
                        <