coreBugZJ

此 blog 已弃。

最长路——算法作业 3.3,EOJ 1110

最长路

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, -1sizeof( 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 


posted on 2011-04-18 16:11 coreBugZJ 阅读(392) 评论(0)  编辑 收藏 引用 所属分类: 课内作业


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理