/*
最短路+最小生成树
题意:给定一张图,起点,终点。求起点到终点的一条路(这条路经过的最长的一段要最短!)
枚举这条“最长的路”,可二分,也可直接计算出。
*/
#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);
}
}
分享到:
相关推荐
基于芯海开发的IDE平台CSU-IDE使用教程
基于photo shop软件全人工标注的混凝土裂隙数据集CSU-Crack(涵盖了常见混凝土特定应用场景图像,包括隧道内壁裂隙、路面裂隙、地上建筑表面裂隙,为裂隙图像识别算法的研究及后续裂隙参数数字表征提供研究数据)....
CSU-Global-MIS581_Capstone_Thesis:SAS Enterprise Miner的CSU-Global MIS581顶点论文代码
csu-thesis:中南大学学术论文LaTex模板。
通过矿物浮选实验、吸附量测试以及红外光谱分析,研究CSU-A与黄铜矿和黄铁矿相互作用的规律.浮选实验结果表明,当CSU-A的质量浓度为6mg/L,溶液pH值为9 .0~9 .5时,CSU
CSU88RP1185D+CS1239标准公版原理图额温枪公版原理图+PCB+封装库文件
辅助研究存放有关CSU-F UX和UX Research简介的信息的地方
这是CSU模拟电子技术B的仿真研讨分数为A的例子。给大家做一个参考!书上内容弄明白为计算机组成原理打好基础就可以了。
The W79E825 series are an 8-bit Turbo 51 microcontroller which has an in-system programmable ... The instruction set of the W79E825 series are fu lly compatible with the standard 8052....
CSU8ASM-IDE V1.3.5
C-Free是一款支持多种编译器的专业化C/C 集成开发环境(IDE)。利用本软件,使用者可以轻松地编辑、编译、连接、运行、调试C/C 程序。C-Free中集成了C/C 代码解析器,能够实时解析代码,并且在编写的过程中给出智能...
#欢迎来到这个 OSX Csu-85 wiki! ##构建丢失的Mac“crt0.o”文件 您是否注意到简单地将 GNU 配置标志应用于静态链接可执行文件对于更复杂的软件包分发失败? 您是否编译过抱怨找不到 crt0.o 的代码? 你并不孤单。...
一个总结poj上面的题目归类,嘿嘿,实在没分,所以,体谅一下。。。想下载东西。。。
中央包装 CSU Primo中央套餐
芯海MCU开发工具选型手册芯海8位MCU软硬件开发平台CSU-IDE集成开发环境CSU8ICE-Lite简易仿真器CSWrite烧录器
项目此回购已使用初始模板填充,以帮助您入门。 请确保更新内容,以为社区建设创造良好的体验。 作为该项目的维护者,请进行一些更新: 改进此README.MD文件可提供出色的体验使用有关该项目的支持经验的内容更新...
CSU CS WIKI 语言: | 关于项目 本项目开源了部分 CS 专业的课程实验与课程设计的源码,我们同时还架设了一个 Wiki 网站,我们的核心想法是: 为代码开源做点贡献 通过 Wiki 中对知识点的扩展,帮助大家更好地了解学...
CSU8ASM-IDE开发编译软件
IDE使用手册,IDE入门,简述IDE的使用