CSU-1307-CityTour+Dij+Kruskal

/*
最短路+最小生成树
题意：给定一张图，起点，终点。求起点到终点的一条路（这条路经过的最长的一段要最短！）
	枚举这条“最长的路”，可二分，也可直接计算出。
*/
#include
#include
#include
#include
#include
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.valy ) 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;iedge[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);
	}
}