1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std ; 6 long long int gcd ( long long int a , long long int b ) 7 { 8 return b ? gcd ( b , a % b ): a ; 9 } 10 int main () 11 { 12 long long int v1 , d1 , v2 , d2 , cas = 1 ; 13 while ( cin >> v1 >> d1 >> v2 >> d2 && ( v1 != 0 || v2 != 0 || d1 != 0 || d2 != 0 )) 14 { 15 long long int a = d1 * v2 , b = d2 * v1 ; 16 if ( a < b ) printf ( "Case #%lld: You owe me a beer!\n" , cas ++); 17 else if ( a > b )...
解題: 1. 利用Floyd Warshall algorithm找出All pairs shortest path 2. 將所有點到fire station的最短距離算出,存於path[i],path[i]中最大值為dd 3. 窮舉所有點當作新的fire station,找出擁有最小的最大值ansd的短即為答案所求的點 Code: #include<stdio.h> #include<stdlib.h> #include<iostream> #include<algorithm> #include<sstream> #include<string.h> using namespace std ; #define MAXN 505 #define INF 10000000 int map [ 505 ][ 505 ]; int dis [ 505 ][ 505 ]; void floy_dp ( int n ) { for ( int k = 1 ; k <= n ; k ++) for ( int i = 1 ; i <= n ; i ++) for ( int j = 1 ; j <= n ; j ++) { if ( dis [ i ][ k ]+ dis [ k ][ j ]< dis [ i ][ j ]) ...
留言
張貼留言