qwq 样例过了,提交全WA
查看原帖
qwq 样例过了,提交全WA
774204
A_chicken_boy楼主2023/8/9 14:52
#include <bits/stdc++.h>
using namespace std ;
#define leng 100001
priority_queue< pair< double , int > > q;
int n , m ;
int head[leng] , dis[leng] , mnext[leng] , ver[leng] , tot ;
int a , b ;
double d[leng] ;
bool p[leng] ;
void add ( int x , int y , int z );
void Dij ( ) ;
int main ( ){
	cin >> n >> m ;
	for ( int i = 1 ; i <= m ; ++i ){
		int c , d , e ;
		cin >> c >> d >> e ;
		add ( c , d , ( 100-e ) );
		add ( d , c , ( 100-e ) ) ;
	}
	cin >> a >> b ;
	Dij ( ) ;
	printf ( "%0.8lf" , d[1] ) ;
	return 0 ;
}
void add ( int x , int y , int z ){
	mnext[++tot] = head[x] ;
	ver[tot] = y ;
	head[x] = tot ;
	dis[tot] = z ;
}
void Dij ( ){
	for ( int i = a ; i <= b ; ++i ){
		d[i] = 347589.00 ;
	}
	d[b] = 100 ;
	q.push(make_pair(d[b],b));
	while ( q.size( ) ){
		int x = q.top( ).second;
	//	cout << x << endl ;
		q.pop( ) ;
		if (p[x])  continue ;
		p[x] = 1 ;
		for ( int i = head[x] ; i ; i = mnext[i] ){
			int y = ver[i] ;
			double z = dis[i] ;
			if ( d[y] >  d[x] * 1.0 * 100.0 / z * 1.0 ){
				d[y] =  d[x] * 1.0 * 100.0 / z * 1.0  ;
				//cout << x << " " << y << " " << d[y]  << endl ;
				q.push(make_pair(-d[y],y));
				//int s = q.top().second ;
				//cout << s <<endl ;
			}
		}
	}
}
2023/8/9 14:52
加载中...