coreBugZJ

此 blog 已弃。

POSTMAN,HUST Monthly 2011.04.09 之 F,1436

POSTMAN

Time Limit: 2 Sec Memory Limit: 128 MB
Submissions: 270 Solved: 29

Description

 

Sam is a postman of the city X, his job is to deliver mails to their destinations. There are N destinations (labeled from 1 to N), one post office (always labeled with 0), and M streets connecting these destinations and the post office. Every day Sam start from the post office at time 0, carrying all the mails he should deliver on that day, and then deliver them along the streets. When he reaches a destination at the first time, he will hand the mail to the person at that destination immediately.

The dissatisfaction of one person is the time he should wait until he receives his mail. Sam wants to design a route in order to minimize the total dissatisfaction of these N persons.

 

Input

 

The first line is an integer T indicating the number of test cases.

Next T block, each block is a test case.

First line of each block is two integers N, M (1 <= N <= 15, 0 <= M <= 200)

Followed by M lines, each line is three integers A B C, indicating that there is a street whose length is C between A and B. (0 <= A, B <= N, 0 < C < 10,000)

 

Output

If Sam can deliver all these N mails to their destinations output the minimum dissatisfaction, otherwise output -1.

 

Sample Input

1
3 6
0 1 1
0 2 4
0 3 3
1 2 2
1 3 2
2 3 10

Sample Output

11
 
f[i][j]  若 j&(1<<k) 则表示 k 已经送达,否则,未送达,在此情况下,邮递员处于 i 时的最小总代价,类似 SPFA 的方式迭代更新。。。
 1#include <iostream>
 2#include <cstdio>
 3#include <cstring>
 4
 5using namespace std;
 6
 7const int N   = 17;
 8const int N2  = (1<<N);
 9const int INF = 0x3f3f3f3f;
10
11int n, n2, w[ N ][ N ], f[ N ][ N2 ];
12
13int  solve() {
14#define  QL  (N*N2)
15        static int queI[ QL ], queJ[ QL ], inq[ N ][ N2 ];
16
17        int i, j, k, nj, t, qh = 0, qt = 1;
18        int ans, tmp;
19
20        queI[ qh ] = 0;
21        queJ[ qh ] = 1;
22        memset( inq, 0sizeof(inq) );
23        inq[ 0 ][ 1 ] = 1;
24        f[ 0 ][ 1 ] = 0;
25        while ( qh != qt ) {
26                i = queI[ qh ];
27                j = queJ[ qh ];
28                inq[ i ][ j ] = 0;
29                qh = ( qh + 1 ) % QL;
30
31                t = 0;
32                for ( k = 0; k < n; ++k ) {
33                        if ( (j&(1<<k)) == 0 ) {
34                                ++t;
35                        }

36                }

37
38                for ( k = 0; k < n; ++k ) {
39                        if ( w[i][k] == INF ) {
40                                continue;
41                        }

42                        nj = ( j|(1<<k) );
43                        tmp = f[ i ][ j ] + w[ i ][ k ] * t;
44                        if ( f[ k ][ nj ] > tmp ) {
45                                f[ k ][ nj ] = tmp;
46                                if ( inq[ k ][ nj ] == 0 ) {
47                                        inq[ k ][ nj ] = 1;
48                                        queI[ qt ] = k;
49                                        queJ[ qt ] = nj;
50                                        qt = ( qt + 1 ) % QL;
51                                }

52                        }

53                }

54        }

55
56        ans = INF;
57        for ( i = 0; i < n; ++i ) {
58                if ( f[ i ][ n2-1 ] < ans ) {
59                        ans = f[ i ][ n2-1 ];
60                }

61        }

62        return ( (ans!=INF) ? ans : (-1) );
63}

64
65int main() {
66        int td, i, j, k, m;
67        scanf( "%d"&td );
68        while ( td-- > 0 ) {
69                memset( w, 0x3fsizeof(w) );
70                memset( f, 0x3fsizeof(f) );
71                scanf( "%d%d"&n, &m );
72                ++n;
73                n2 = (1<<n);
74                while ( m-- > 0 ) {
75                        scanf( "%d%d%d"&i, &j, &k );
76                        if ( k < w[ i ][ j ] ) {
77                                w[ i ][ j ] = w[ j ][ i ] = k;
78                        }

79                }

80                for ( i = 0; i < n; ++i ) {
81                        w[ i ][ i ] = INF;
82                }

83                printf( "%d\n", solve() );
84        }

85        return 0;
86}

87

posted on 2011-04-09 18:49 coreBugZJ 阅读(844) 评论(0)  编辑 收藏 引用 所属分类: ACM


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理