HDU 2112 HDU Today

题目链接~~>

做题感悟：这题很多坑的地方，比如起点与终点相同，最多150个站点。哎~还是被坑的太少。

解题思路：map+DIjkstra 可以用map处理字符串，但是用时比普通数组花时间长。

代码：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<string>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #include<math.h>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      const int INF = 99999999 ;
     
    
   

    

     

    
    

     

      const int MX = 155 ;
     
    
   

    

     

    
    

     

      int g[MX][MX],r ;
     
    
   

    

     

    
    

     

      bool vis[MX] ;
     
    
   

    

     

    
    

     

      int d[MX] ;
     
    
   

    

     

    
    

     

      string str1,str2 ;
     
    
   

    

     

    
    

     

      void Dijkstra()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 memset(vis,false,sizeof(vis)) ;
     
    
   

    

     

    
    

     
 for(int i=1 ;i<=r ;i++)
     
    
   

    

     

    
    

     

       d[i]=INF ;
     
    
   

    

     

    
    

     

       d[1]=0 ;
     
    
   

    

     

    
    

     
 for(int i=1 ;i<=r ;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 int min=INF,sx ;
     
    
   

    

     

    
    

     
 for(int j=1 ;j<=r ;j++)
     
    
   

    

     

    
    

     
 if(!vis[j]&&d[j]<min)
     
    
   

    

     

    
    

     

       min=d[sx=j] ;
     
    
   

    

     

    
    

     
 if(min==INF)  break ; // 最好加个
     
    
   

    

     

    
    

     

       vis[sx]=true ;
     
    
   

    

     

    
    

     
 for(int j=1 ;j<=r ;j++)
     
    
   

    

     

    
    

     
 if(d[sx]+g[sx][j]<d[j])
     
    
   

    

     

    
    

     

       d[j]=d[sx]+g[sx][j] ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 map<string,int>m ;
     
    
   

    

     

    
    

     
 int x,n ;
     
    
   

    

     

    
    

     
 char s1[200],s2[200] ;
     
    
   

    

     

    
    

     
 while(~scanf("%d",&n)&&n!=-1)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       m.clear() ;
     
    
   

    

     

    
    

     
 bool flag=false ;
     
    
   

    

     

    
    

     
 scanf("%s%s",s1,s2) ;
     
    
   

    

     

    
    

     
 if(!strcmp(s1,s2))  flag=true ;
     
    
   

    

     

    
    

     

       m[s1]=1 ;
     
    
   

    

     

    
    

     

       m[s2]=2 ;
     
    
   

    

     

    
    

     

       r=3 ;
     
    
   

    

     

    
    

     
 for(int i=1 ;i<152 ;i++)
     
    
   

    

     

    
    

     
 for(int j=1 ;j<152 ;j++)
     
    
   

    

     

    
    

     

       g[i][j]=INF ;
     
    
   

    

     

    
    

     
 for(int i=0 ;i<n ;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%s%s%d",s1,s2,&x) ;
     
    
   

    

     

    
    

     
 if(!m[s1])m[s1]=r++ ;
     
    
   

    

     

    
    

     
 if(!m[s2])m[s2]=r++ ;
     
    
   

    

     

    
    

     
 if(g[m[s1]][m[s2]]>x)// 注意重边（这样的数据这题没有）
     
    
   

    

     

    
    

     

       g[m[s1]][m[s2]]=g[m[s2]][m[s1]]=x ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if(flag)// 注意起始站相同的情况
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 printf("0\n") ;
     
    
   

    

     

    
    

     
 continue ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       Dijkstra() ;
     
    
   

    

     

    
    

     
 printf("%d\n",d[2]==INF ? -1 : d[2]) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/20470761