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 已經(jīng)送達(dá)，否則，未送達(dá)，在此情況下，郵遞員處于 i 時(shí)的最小總代價(jià)，類似 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
13
int 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, 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;
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, 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