最長路
Time Limit:1000MS
Memory Limit:30000KB
Total Submit:569
Accepted:172
Description
設G為有n個頂點的有向無環圖，G中各頂點的編號為1到n，且當<i，j>為G中的一條邊時有i <
j。設w（i，j）為邊<i，j>的長度，請設計動態規劃算法，計算圖G中<i，j>間的最長路徑。輸入一個n，表示這個圖中有
n個頂點，后一個m，表示有m對路徑<i，j>，有向，后一個數p,表示有p次詢問，在接下來的p行中每行輸入2個數a,b，算出此圖中從a
到b的最長路徑。
Input
輸入一個數n(1<=n<=200)，表示有n個點，接下來一個數m，表示有m條路，接下來m行中每行輸入2個數a ，b，v表示從a點到b點有條路，路的長度為v。
接下來輸入一個數p，表示有p次詢問，在接下來的p行中每行輸入2個數a,b，算出此圖中從a到b的最長路徑。
Output
對每個詢問p，(a,b)，輸出從a到b之間的最長路.如果a,b之間沒連通，輸出－1。
Sample Input
4 4
1 2 2
2 3 3
1 3 4
3 4 2
3
1 2
1 3
1 4
Sample Output
2
5
7
Source
ECNU算法作業
Floyd 算法：
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4
5 using namespace std;
6
7 int main(){
8 const int N = 203;
9 int w[ N ][ N ], n, m, i, j, k, p;
10
11 while( EOF != scanf( "%d%d", &n, &m ) ){
12 memset( w, -1, sizeof( w ) );
13 while( m-- ){
14 scanf( "%d%d%d", &i, &j, &k );
15 if( k > w[ i ][ j ] ){
16 w[ i ][ j ] = k;
17 }
18 }
19 for( i = 1; i <= n; ++i ){
20 w[ i ][ i ] = 0;
21 }
22 for( k = 1; k <= n; ++k ){
23 for( i = 1; i <= n; ++i ){
24 for( j = 1; j <= n; ++j ){
25 if( ( k != i ) && ( k != j ) && ( i != j ) && ( w[ i ][ k ] >= 0 ) && ( w[ k ][ j ] >= 0 ) && ( w[ i ][ k ] + w[ k ][ j ] > w[ i ][ j ] ) ){
26 w[ i ][ j ] = w[ i ][ k ] + w[ k ][ j ];
27 }
28 }
29 }
30 }
31 scanf( "%d", &p );
32 while( p-- ){
33 scanf( "%d%d", &i, &j );
34 printf( "%d\n", w[ i ][ j ] );
35 }
36 }
37
38 return 0;
39 }
40