一、题目大意

无向图，给出邻接矩阵的下半矩阵，要求源点1，到其他点最短时间（散播整个网络的最短时间）。

二、AC code

明显的单源最短路径

但是还是用了Floyd算法撞撞运气，毕竟是无向图，当然可以对Floyd优化，最后也可以A。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               //#include 
               #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #define INF 0x3f3f3f3fusing namespace std;template 
                    
                     Type stringToNum(const string& str){ istringstream iss(str); Type num; iss >> num; return num; }//======================================================#define MAXN 102int map[MAXN][MAXN];int main(){ //freopen("input.txt","r",stdin); int n; cin >> n; for (int i = 2; i <= n; ++i) { for (int j = 1; j < i; ++j) { string s; cin>>s; int tmp = INF; if(s != "x"){ tmp = stringToNum
                     
                       (s); } map[j][i] = map[i][j] = tmp; } } //floyd for (int k = 1; k <= n; ++k) { for (int i = 1; i <= n; ++i) { for (int j = 1; j < i; ++j) { map[j][i] = map[i][j] = min(map[i][j],map[i][k]+map[k][j]); } } } int time = -1; for (int i = 2; i <= n ; ++i) { time = time > map[1][i]? time : map[1][i]; } cout<
                      <

dijkstra：

重定向忘记删掉，WA一次，甚是可惜

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               //#include 
               #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #define INF 0x3f3f3f3fusing namespace std;template 
                    
                     Type stringToNum(const string& str){ istringstream iss(str); Type num; iss >> num; return num; }//======================================================#define MAXN 102int map[MAXN][MAXN];bool visited[MAXN];void update(int minPos,int n) { for (int i = 1; i <= n; ++i) { if( !visited[i] && map[1][i] > map[1][minPos] + map[minPos][i] ) map[i][1] = map[1][i] = map[1][minPos] + map[minPos][i]; }}void dijkstra(int n) { visited[1] = 1; while(1) { int tmpMin = INF; int minPos = -1; for (int i = 2; i <= n; ++i) { if( !visited[i] && tmpMin > map[1][i] ) { //have not been visited && smaller tmpMin = map[1][i]; minPos = i; } } if( -1 == minPos ) break; visited[minPos] = 1; update(minPos,n); //update the map, if it's shorter to get through minPos }}int main(){ //freopen("input.txt","r",stdin); int n; cin >> n; for (int i = 2; i <= n; ++i) { for (int j = 1; j < i; ++j) { string s; cin>>s; int tmp = INF; if(s != "x"){ tmp = stringToNum
                     
                       (s); } map[j][i] = map[i][j] = tmp; } } dijkstra(n); int time = -1; for (int i = 2; i <= n ; ++i) { time = time > map[1][i]? time : map[1][i]; } cout<
                      <