最长路
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