hdu 1599 find the mincost route

点击打开链接hdu 1599

思路：最短路+floyd+最小环

分析：
1 题目要求的是能否有从某一个点出发至少经过两个不同点然后回到源点，有的话求最小路径长度。
2 题意很明确就是要求最小环问题 ， 所以现在用到了floyd的一个扩展求解图上最小环。
3 <<floyd求解环中的最小环>>
1 为什么要在更新最短路之前求最小环：
在第k层循环，我们要找的是最大结点为k的环，而此时Dist数组存放的是k-1层循环结束时的经过k-1结点的最短路径，也就是说以上求出的最短路是不经过k点的，这就刚好符合我们的要求。为什么呢？假设环中结点i,j是与k直接相连，如果先求出经过k的最短路，那么会有这样一种情况，即：i到j的最短路经过k。这样的话就形成不了环 。

2最小环改进算法的证明：
一个环中的最大结点为k(编号最大)，与他相连的两个点为i,j，这个环的最短长度为g[i][k]+g[k][j]+dis[i][j] (i到j的路径中,所有结点编号都小于k的最短路径长度)。根据floyd的原理，在最外层循环做了k-1次之后，dist[i][j]则代表了i到j的路径中，所有结点编号都小于k的最短路径, 综上所述，该算法一定能找到图中最小环。

3 为什么还要value数组：
因为dis数组时刻都在变动不能表示出原来两个点之间的距离。

4 形成环至少要有3点不同的点，两个点是不能算环的，所以有i , j , k不同。

4 注意：hdu有时候比较特别，你使用long long的话oj给的是WA，这一题我用long long WA了，所以用int。

5 代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 110
#define INF 0xFFFFFFF

int n , m;
int mincircle;
int dis[MAXN][MAXN];
int value[MAXN][MAXN];

/*初始化value数组*/
void init(){
   for(int i = 1 ; i <= n ; i++){
      for(int j = 1 ; j <= n ; j++)
         value[i][j] = dis[i][j] = INF;
      value[i][i] = dis[i][i] = 0;
   }
}

int min(int  a , int b){
    return a < b ? a : b;
}

void floyd(){
    mincircle = INF;
    for(int k = 1 ; k <= n ; k++){
       /*找最小环，i , j , k三点不同*/
       for(int i = 1 ; i < k ; i++){
          for(int j = i+1 ; j < k ; j++){
               mincircle = min(mincircle , dis[i][j]+value[i][k]+value[k][j]);
          }
       }
       /*求解最短路*/
       for(int i = 1 ; i <= n ; i++){
          for(int j = 1 ; j <= n ; j++){
              dis[i][j] = min(dis[i][j] , dis[i][k]+dis[k][j]);
          }
       }
    }
}

int main(){
   int a , b , v;
   while(scanf("%d%d" , &n , &m) != EOF){
       init();
       for(int i = 0 ; i < m ; i++){
          scanf("%d%d%d" , &a , &b , &v);
          if(dis[a][b] > v){
            dis[a][b] = dis[b][a] = v;
            value[a][b] = value[b][a] = v;
          }
       }
       floyd();
       if(mincircle == INF)
         printf("It's impossible.\n");
       else
         printf("%d\n" , mincircle);
   }
   return 0;
}