CSU-1307-CityTour+Dij+Kruskal

/*
最短路+最小生成樹
題意：給定一張圖，起點，終點。求起點到終點的一條路（這條路經過的最長的一段要最短！）
	枚舉這條“最長的路”，可二分，也可直接計算出。
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<queue>
using namespace std;

const int maxn = 2005;
const int maxm = 50005;
const int inf = 99999999;

int mat[ maxn ][ maxn ];
int fa[ maxn ];
bool vis[ maxn ];
int dis[ maxn ];
struct Node{
	int x,y,val;
}edge[ maxm<<1 ];

int cmp( Node a,Node b ){
	return a.val<b.val;
}

void init( int n ){
	for( int i=1;i<=n;i++ ){
		fa[ i ] = i;
		for( int j=1;j<=n;j++ ){
			mat[i][j] = inf;
		}
	}
}

int find( int x ){
	if( x==fa[x] ) 
		return x;
	return fa[x] = find(fa[x]);
}

int Kruskal( int n,int m,int A,int B ){
	sort( edge,edge+m,cmp );
	int x,y;
	int MaxEdge = 0;
	for( int i=0;i<m;i++ ){
		x = find( edge[i].x );
		y = find( edge[i].y );
		if( x!=y ){
			if( x>y ) fa[y] = x;
			else fa[x] = y;
			if( find(A)==find(B) ){
				MaxEdge = edge[i].val;
				return MaxEdge;
			}
			MaxEdge = max( MaxEdge,edge[i].val );
		}
	}
	return MaxEdge;
}

int Dij( int n,int MaxEdge,int A,int B ){
	for( int i=1;i<=n;i++ ){
		vis[i] = false;
		dis[i] = inf;
	}
	dis[ A ] = 0;
	for( int i=1;i<=n;i++ ){
		int M = inf;
		int id = -1;
		for( int j=1;j<=n;j++ ){
			if( !vis[j] && M>dis[j] ){
				M = dis[j];
				id = j;
			}
		}
		if( id==-1 ) break;
		vis[ id ] = true;
		for( int j=1;j<=n;j++ ){
			if( !vis[j] && dis[j]>dis[id]+mat[id][j] && mat[id][j]<=MaxEdge ){
				dis[j] = dis[id]+mat[id][j];
			}
		}
	}
	return dis[B];
}

int main(){
	//freopen("in.txt","r",stdin);
	int n,m,A,B;
	while( scanf("%d%d%d%d",&n,&m,&A,&B)!=EOF ){
		init( n );
		for( int i=0;i<m;i++ ){
			scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].val);
			if( mat[edge[i].x][edge[i].y]>edge[i].val ){
				mat[edge[i].x][edge[i].y] = mat[edge[i].y][edge[i].x] = edge[i].val;
			}
		}
		int MaxEdge = 0;
		MaxEdge = Kruskal( n,m,A,B );
		//printf("MaxEdge = %d\n",MaxEdge);
		int Sum = Dij( n,MaxEdge,A,B );
		printf("%d\n",Sum);
	}
}