20210524考试—景区路线规划题解


#include
#include
#include
#define printf Ruusupuu=printf
#define R register int
#define int long long
using namespace std ;
const int N = 3e2 + 10 ;
typedef long long L ;
typedef double D ;
inline int read(){
int w = 0 ; bool fg = 0 ; char ch = getchar() ;
while( ch <‘0‘ || ch > ‘9‘ ) fg |= ( ch == ‘-‘ ) , ch = getchar() ;
while( ch >= ‘0‘ && ch <= ‘9‘ ) w = ( w <<1 ) + ( w <<3 ) + ( ch - ‘0‘ ) , ch = getchar() ;
return fg ? -w : w ;
}
int Ruusupuu , n , m , k , cnt , head [N] , xs , ys , ws ;
struct P{ int c , h1 , h2 ; D p ; } b [N] ;
struct E{ int fr , to , next , w ; } a [N <<6] ;
D ans1 , ans2 ;
inline void add( int f , int t , int w ){
a [++ cnt].fr = f ;
a [cnt].to = t ;
a [cnt].w = w ;
a [cnt].next = head [f] ;
head [f] = cnt ;
}
inline void dfs( int x , int lef , D p ){
// printf( "THIS DFS%ld %ld\n" , x , lef ) ;
b [x].p += p ;
int gnt = 0 ;
for( R i = head [x] ; ~i ; i = a [i].next ){
int y = a [i].to ;
// printf( "%ld %ld %ld %ld\n" , x , y , lef , lef - a [i].w - b [y].c ) ;
if( lef - a [i].w - b [y].c >= 0 ) gnt ++ ;
}
for( R i = head [x] ; ~i ; i = a [i].next ){
int y = a [i].to ;
if( lef - a [i].w - b [y].c >= 0 )
dfs( y , lef - a [i].w - b [y].c , p / (D) gnt ) ;
}
}
void sc(){
n = read() , m = read() , k = read() ; memset( head , -1 , sizeof( head ) ) ;
for( R i = 1 ; i <= n ; i ++ ) b [i].c = read() , b [i].h1 = read() , b [i].h2 = read() ;
for( R i = 1 ; i <= m ; i ++ ) xs = read() , ys = read() , ws = read() , add( xs , ys , ws ) , add( ys , xs , ws ) ;
}
void work(){
for( R i = 1 ; i <= n ; i ++ ) dfs( i , k - b [i].c , 1.0 / (D) n ) ;
for( R i = 1 ; i <= n ; i ++ ) ans1 += (D) b [i].h1 * b [i].p , ans2 += (D) b [i].h2 * b [i].p ;
printf( "%.5lf %.5lf\n" , ans1 , ans2 ) ;
}
signed main(){
sc() ;
work() ;
return 0 ;
}