★ 夢想生活 ｜成長記事本 ★

解題： 利用Floyd Warshall找出起點至任意點的距離，再找最大值就是答案 (p.s.和UVa 11463很像) Code： #include<stdio.h> #include<stdlib.h> #include<iostream> #include<algorithm> #include<string.h> #define INF 100000 using namespace std ; int dis [ 105 ][ 105 ]; int initial ( int n ) {     for ( int i = 1 ; i <= n ; i ++)         for ( int j = 1 ; j <= n ; j ++) dis [ i ][ j ]=( i == j )? 0 : INF ; } int Floyd ( 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 ])     ...

解題： 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 ])         ...