其实这道题根本不用最短路算法...
我们可以就把边从小到大排序,那么只需要枚举大小两个端点,把中间的边都加进去判断联通性即可.
判断联通性显然用的是并查集.
#include <cstdio>
#include <algorithm>
struct DJSET{
struct{
int fa,rk;
} p[505];
int find(int k){ return p[k].fa?p[k].fa=find(p[k].fa):k; }
inline void merge(int a,int b){
a=find(a),b=find(b);
if(a==b) return;
if(p[a].rk<p[b].rk) std::swap(a,b);
p[b].fa=a;
if(p[a].rk==p[b].rk) ++p[a].rk;
}
} set[5005];
struct eg{
int f,t,l;
inline void read(){
scanf("%d%d%d",&f,&t,&l);
}
} Es[5005];
int gcd(int a,int b){
if(a) return gcd(b%a,a);
return b;
}
bool cmp(const eg& a,const eg& b){
return a.l<b.l;
}
int m,n,i,j,s,t;
int FA,FB,FC,FA1,FB1,FC1;
inline void reduce(){
FC=gcd(FA,FB);
FA/=FC,FB/=FC;
}
int main(){
scanf("%d%d",&n,&m);
for(i=0;i<m;++i) Es[i].read();
std::sort(Es,Es+m,cmp);
scanf("%d%d",&s,&t);
FA1=1000;
for(i=0;i<m;++i){
for(j=i;j<m;++j){
set[i].merge(Es[j].f,Es[j].t);
if(set[i].find(s)==set[i].find(t)){
FA=Es[j].l,FB=Es[i].l;
reduce();
if(FA*FB1<FB*FA1){
FA1=FA;
FB1=FB;
}
break;
}
}
}
if(FB1==0) printf("IMPOSSIBLE"); else{
if(FB1==1) printf("%d
",FA1); else printf("%d/%d
",FA1,FB1);
}
return 0;
}
其实有个小优化:当所有边都加入而不联通时直接退出IMPOSSIBLE.
然后哎唷我擦快了不少...
#include <cstdio>
#include <algorithm>
struct DJSET{
struct{
int fa,rk;
} p[505];
int find(int k){ return p[k].fa?p[k].fa=find(p[k].fa):k; }
inline void merge(int a,int b){
a=find(a),b=find(b);
if(a==b) return;
if(p[a].rk<p[b].rk) std::swap(a,b);
p[b].fa=a;
if(p[a].rk==p[b].rk) ++p[a].rk;
}
} set[5005];
struct eg{
int f,t,l;
inline void read(){
scanf("%d%d%d",&f,&t,&l);
}
} Es[5005];
int gcd(int a,int b){
if(a) return gcd(b%a,a);
return b;
}
bool cmp(const eg& a,const eg& b){
return a.l<b.l;
}
int m,n,i,j,s,t;
int FA,FB,FC,FA1,FB1,FC1;
inline void reduce(){
FC=gcd(FA,FB);
FA/=FC,FB/=FC;
}
int main(){
scanf("%d%d",&n,&m);
for(i=0;i<m;++i) Es[i].read();
std::sort(Es,Es+m,cmp);
scanf("%d%d",&s,&t);
FA1=1000;
for(i=0;i<m;++i){
for(j=i;j<m;++j){
set[i].merge(Es[j].f,Es[j].t);
if(set[i].find(s)==set[i].find(t)){
FA=Es[j].l,FB=Es[i].l;
reduce();
if(FA*FB1<FB*FA1){
FA1=FA;
FB1=FB;
}
break;
}
}
if(FB1==0){
printf("IMPOSSIBLE
");
return 0;
}
}
if(FB1==1) printf("%d
",FA1); else printf("%d/%d
",FA1,FB1);
return 0;
}
由于空间够大我还偷了个懒没有每次memset一遍...然后就出现了奇异的景象:
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
2W多KB的那个SB就是我.