# coreBugZJ

## 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.

```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;1011int n, n2, w[ N ][ N ], f[ N ][ N2 ];1213int  solve() {14#define  QL  (N*N2)15        static int queI[ QL ], queJ[ QL ], inq[ N ][ N2 ];1617        int i, j, k, nj, t, qh = 0, qt = 1;18        int ans, tmp;1920        queI[ qh ] = 0;21        queJ[ qh ] = 1;22        memset( inq, 0, sizeof(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;3031                t = 0;32                for ( k = 0; k < n; ++k ) {33                        if ( (j&(1<<k)) == 0 ) {34                                ++t;35                        }36                }3738                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        }5556        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}6465int main() {66        int td, i, j, k, m;67        scanf( "%d", &td );68        while ( td-- > 0 ) {69                memset( w, 0x3f, sizeof(w) );70                memset( f, 0x3f, sizeof(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 阅读(852) 评论(0)  编辑 收藏 引用 所属分类: ACM