最長(zhǎng)路
Time Limit:1000MS
Memory Limit:30000KB
Total Submit:569
Accepted:172
Description
設(shè)G為有n個(gè)頂點(diǎn)的有向無(wú)環(huán)圖，G中各頂點(diǎn)的編號(hào)為1到n，且當(dāng)<i，j>為G中的一條邊時(shí)有i <
j。設(shè)w（i，j）為邊<i，j>的長(zhǎng)度，請(qǐng)?jiān)O(shè)計(jì)動(dòng)態(tài)規(guī)劃算法，計(jì)算圖G中<i，j>間的最長(zhǎng)路徑。輸入一個(gè)n，表示這個(gè)圖中有
n個(gè)頂點(diǎn)，后一個(gè)m，表示有m對(duì)路徑<i，j>，有向，后一個(gè)數(shù)p,表示有p次詢問(wèn)，在接下來(lái)的p行中每行輸入2個(gè)數(shù)a,b，算出此圖中從a
到b的最長(zhǎng)路徑。
Input
輸入一個(gè)數(shù)n(1<=n<=200)，表示有n個(gè)點(diǎn)，接下來(lái)一個(gè)數(shù)m，表示有m條路，接下來(lái)m行中每行輸入2個(gè)數(shù)a ，b，v表示從a點(diǎn)到b點(diǎn)有條路，路的長(zhǎng)度為v。
接下來(lái)輸入一個(gè)數(shù)p，表示有p次詢問(wèn)，在接下來(lái)的p行中每行輸入2個(gè)數(shù)a,b，算出此圖中從a到b的最長(zhǎng)路徑。
Output
對(duì)每個(gè)詢問(wèn)p，(a,b)，輸出從a到b之間的最長(zhǎng)路.如果a,b之間沒(méi)連通，輸出－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算法作業(yè)
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