HDU Problem 1599 find the mincost route 【Floyd求最小环】-白红宇

HDU Problem 1599 find the mincost route 【Floyd求最小环】

阅读量：6986 次

发布时间：2019-06-27

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

Time Limit: 1000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 4300 Accepted Submission(s): 1725

Problem Description

杭州有N个景区，景区之间有一些双向的路来连接，现在8600想找一条旅游路线，这个路线从A点出发并且最后回到A点，假设经过的路线为V1,V2,....VK,V1,那么必须满足K>2,就是说至除了出发点以外至少要经过2个其他不同的景区，而且不能重复经过同一个景区。现在8600需要你帮他找一条这样的路线，并且花费越少越好。

Input

第一行是2个整数N和M（N <= 100, M <= 1000)，代表景区的个数和道路的条数。

接下来的M行里，每行包括3个整数a,b,c.代表a和b之间有一条通路，并且需要花费c元(c <= 100)。

Output

对于每个测试实例，如果能找到这样一条路线的话，输出花费的最小值。如果找不到的话，输出"It's impossible.".

Sample Input

      3 3 1 2 1 2 3 1 1 3 1 3 3 1 2 1 1 2 3 2 3 1 

Sample Output

      3 It's impossible. 

Author

8600

Source

Recommend

8600 | We have carefully selected several similar problems for you:

如果理解了Floyd算法的过程就会发现，当存在d[i][j] + u[j][k] + d[k][i] != INF的时候会出现一个环，因为更新的时候u没有参与，所以同原来的路径表示。每次更新环的最小值就是答案。

#include #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 //#include 
                 
                  #define space " "using namespace std;//typedef long long LL;//typedef __int64 Int;typedef pair
                  
                    paii;const int INF = 99999999;const double ESP = 1e-5;const double Pi = acos(-1.0);const int MOD = 1e9 + 7;const int MAXN = 100 + 10;int n,m,minn;int d[MAXN][MAXN], a[MAXN][MAXN];void floyd() { minn = INF; for(int k = 1;k <= n; k++) { for(int i = 1; i < k; i++) { for(int j = 1; j < i; j++) { minn = min(minn, d[i][j] + a[i][k] + a[k][j]); } } for(int i = 1; i <= n; i++) { for(int j = 1;j <= n; j++) { d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } } }}int main() { int p, q, len; while(scanf("%d%d", &n, &m) != EOF) { for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { a[i][j] = INF; } } for(int i = 1; i <= m; i++) { scanf("%d%d%d", &p, &q, &len); if(len < a[p][q]) a[p][q] = a[q][p] = len; } for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { d[i][j] = a[i][j]; } } floyd(); if(minn != INF) printf("%d\n", minn); else printf("It's impossible.\n"); } return 0;}

转载于:https://www.cnblogs.com/cniwoq/p/6770801.html

你可能感兴趣的文章