hdu 1595 find the longest of the shotest（Dijkstra）

テーマリンク:http://acm.hdu.edu.cn/showproblem.php?pid=1595
find the longest of the shotest
Time Limit：1000/5000 MS（Java/Others）    メモリLimit：32768/32768 K（Java/Others）
Total Submission(s)：1665    Acceepted Submission(s)：588
Problem Description
Marica is very angry with Mirko because he found a new girlfriend and she seeks reventage.Since she doesn't live in the same city，she started preparing for the long Journey.We know for everry End hold and and and and and and and and proad hold compone minit compone compone minit
Mirko overheard in the car that one of the road s is under repairs，and that it is blocked，but didn't konw exactly which road.It is possible to come from Markica's cityto Mirko'sのmatch cled.
Marica will travel only by non-blocked roads、and she will travel by shot route.Mirko wants to know how long will it Tale for her to get to his city in the wost case、so that he could make sure that his girlfriend is out of town for long enough.Write a program that helps Mirko in finding out what the longest time in minutes it could for Markica coult by shot blit
 
Input
Each case there re re two numbers in the first row，N and M，separated by a single space，the number of towns，and the number of roads between the towns.1≦N≦m≦N*(N-1)/2.Themartics fress 1
In the next M lines are three numbers A，B and V，separated bycommmas.1≦A，B≦N，1≦V≦100000.Those numbers mean there is a two-road between cities A and B，and that it crossable minutes.V。
 
Output
In the first line of the output file write the maximtime in minutes、it could take Marica to mirko.
 
Sample Input

   
   
   
   

    
    
    
    5 6
1 2 4
1 3 3
2 3 1
2 4 4
2 5 7
4 5 1

6 7
1 2 1
2 3 4
3 4 4
4 6 4
1 5 5
2 5 2
5 6 5

5 7
1 2 8
1 4 10
2 3 9
2 4 10
2 5 1
3 4 7
3 5 10
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    11
13
27
   
   
   
   

 
Author
ailyanlu
 
ソurce
HDU 2007-Spring Programe ming Conttest-Warm Up(1) 
図の中のある経路が遮断されたと仮定すると、その最悪の場合の最短経路はどれぐらいですか？基本的なアルゴリズムは、最初に最短のパスを求めてから、最短のパスの中のいずれかの端が遮断されていると仮定して、最も短絡を求めて、これらの最短の最大値を取ればいいです。
コードは以下の通りです

#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <cstdlib>
#include <climits>
#include <ctype.h>
#include <queue>
#include <stack>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;
#define PI acos(-1.0)
#define INF 0x3fffffff
//typedef long long LL;
//typedef __int64 LL;
#define MAXN 1017
int mat[MAXN][MAXN];
int n, m;
int re[MAXN];//    
void init()
{
	for(int i = 0; i <= n; i++)
	{
		re[i] = 0;
		for(int j = 0 ; j <= n; j++)
		{
			if(i == j)
				mat[i][j] = 0;
			else
				mat[i][j] = INF;
		}
	}
}

int dijkstra (int f)
{
	int dis[MAXN];//           
	int mark[MAXN];//         
	int i,j,k = 0;
	for(i = 0 ; i <= n ; i++)//       ，           
		mark[i] = 0;
    for(i = 0 ; i <= n ; i++)
    {
        dis[i] = INF;
    }
	//	mark[1] = 1;
    dis[1] = 0;//start 1
    int min ;//       。 
    for(i = 1 ; i <= n; i++)
    {
        min = INF;
        for(j = 1 ; j <= n;j++)
        {
            if(mark[j] == 0  && dis[j] < min)//        ，         
            {
                min = dis[j] ;
                k = j;
            }
        }
        mark[k] = 1;//       
        for(j = 1 ; j <= n ; j++)
        {
            if( mark[j] == 0  && (dis[j] > (dis[k] + mat[k][j])))//            
            {
                dis[j] = dis[k] + mat[k][j];
				if(f)
					re[j] = k;
            }
        }
    }
    return dis[n];    
} 

int main()
{
	int i, j;
	int a, b, v;
	while(~scanf("%d%d",&n,&m))
	{
		init();
		for(i = 0; i < m; i++)
		{
			scanf("%d%d%d",&a,&b,&v);
			if(v < mat[a][b])
			{
				mat[a][b] = mat[b][a] = v;
			}
		}
		int ans = dijkstra(1);
		for(i = n; i != 1; i = re[i])
		{
			int t = mat[i][re[i]];
			mat[i][re[i]] = INF;
			mat[re[i]][i] = INF;
			int tt = dijkstra(0);// 0    re[]      
			if( ans < tt)
				ans = tt;
			mat[i][re[i]] = t;
			mat[re[i]][i] = t;
		}
		printf("%d
",ans);
	}
	return 0;
}