# coreBugZJ

## 最长路——算法作业 3.3，EOJ 1110

Time Limit:1000MS Memory Limit:30000KB
Total Submit:569 Accepted:172

Description

Input

Output

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 阅读(312) 评论(0)  编辑 收藏 引用 所属分类: 课内作业