设为首页 加入收藏

TOP

舒适的路线
2014-11-23 20:10:29 来源: 作者: 【 】 浏览:1
Tags:舒适 路线

// File Name: wiki1001.cpp
// Author: bo_jwolf
// Created Time: 2013年08月18日 星期日 08时40分44秒

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define INF 0xffffff
using namespace std;
const int maxn = 5005 ;
struct node
{
int x , y , v ;
bool operator < ( const node a ) const
{
return v < a.v ;
}
}edge[ maxn ] ;

int n , m , s ,t , k , Max , Min ;
int fa[ maxn ] ;

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

int gcd( int a , int b )
{
return b == 0 a : gcd( b , a % b ) ;
}

int main()
{
double ans = INF ;
cin >> n >> m ;
{
for( int i = 1 ; i <= m ; ++ i )
{
cin >> edge[ i ]. x >> edge[ i ].y >> edge[ i ].v ;
}
cin >> s >> t ;
sort( edge + 1 , edge + 1 + m ) ;
for( int i = 1 ; i <= m ; ++i )
{
for( int j = 0 ; j <= n ; ++j )
fa[ j ] = j ;
for( int j = i ; j <= m ; ++j )
{
if( find( edge[ j ].x ) != find( edge[ j ].y) )
fa[ fa[ edge[ j ].x ] ] = fa[ edge[ j ].y ] ;
if( find( s ) == find( t ) )
{
if( edge[ j ].v / 1.0 / edge[ i ].v < ans )
{
Max = edge[ j ].v ;
Min = edge[ i ].v ;
ans = edge[ j ].v / 1.0 / edge[ i ].v ;
}
break ;
}
}
}
if( ans == INF )
cout << "IMPOSSIBLE" << endl ;
else
{
int temp = gcd( Max , Min ) ;
Max /= temp ;
Min /= temp ;
cout << Max ;
if( Min != 1 )
cout << "/" << Min ;
cout << endl ;
}
}
return 0;
}

// File Name: wiki1001.cpp
// Author: bo_jwolf
// Created Time: 2013年08月18日 星期日 08时40分44秒

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define INF 0xffffff
using namespace std;
const int maxn = 5005 ;
struct node
{
int x , y , v ;
bool operator < ( const node a ) const
{
return v < a.v ;
}
}edge[ maxn ] ;

int n , m , s ,t , k , Max , Min ;
int fa[ maxn ] ;

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

int gcd( int a , int b )
{
return b == 0 a : gcd( b , a % b ) ;
}

int main()
{
double ans = INF ;
cin >> n >> m ;
{
for( int i = 1 ; i <= m ; ++ i )
{
cin >> edge[ i ]. x >> edge[ i ].y >> edge[ i ].v ;
}
cin >> s >> t ;
sort( edge + 1 , edge + 1 + m ) ;
for( int i = 1 ; i <= m ; ++i )
{
for( int j = 0 ; j <= n ; ++j )
fa[ j ] = j ;
for( int j = i ; j <= m ; ++j )
{
if( find( edge[ j ].x ) != find( edge[ j ].y) )
fa[ fa[ edge[ j ].x ] ] = fa[ edge[ j ].y ] ;
if( find( s ) == find( t ) )
{
if( edge[ j ].v / 1.0 / edge[ i ].v < ans )
{
Max = edge[ j ].v ;
Min = edge[ i ].v ;
ans = edge[ j ].v / 1.0 / edge[ i ].v ;
}
break ;
}
}
}
if( ans == INF )
cout << "IMPOSSIBLE" << endl ;
else
{
int temp = gcd( Max , Min ) ;
Max /= temp ;
Min /= temp ;
cout << Max ;
if( Min != 1 )
cout << "/" << Min ;
cout << endl ;
}
}
return 0;
}

】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇CodeForces #196(Div. 2) 337D Bo.. 下一篇文件拖拽效果----C++实现

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

·微服务 Spring Boot (2025-12-26 18:20:10)
·如何调整 Redis 内存 (2025-12-26 18:20:07)
·MySQL 数据类型:从 (2025-12-26 18:20:03)
·Linux Shell脚本教程 (2025-12-26 17:51:10)
·Qt教程,Qt5编程入门 (2025-12-26 17:51:07)