• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            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 閱讀(924) 評論(0)  編輯 收藏 引用 所屬分類: ACM

            国产99久久久国产精品小说| 日韩精品久久久肉伦网站 | 久久久国产一区二区三区| 久久成人国产精品| 国产99精品久久| 久久久久久久久久久免费精品| 久久播电影网| 久久婷婷国产综合精品| 99久久久精品| 久久一本综合| 久久综合噜噜激激的五月天| 久久久久中文字幕| 伊人久久精品影院| 日本精品久久久久中文字幕8| 无码任你躁久久久久久老妇| 中文字幕乱码人妻无码久久| 国产精品免费久久久久久久久| 久久久久国产精品人妻| 国产ww久久久久久久久久| 狠狠精品久久久无码中文字幕| 91精品国产91久久久久久青草| 国产精品亚洲综合久久| 99久久无码一区人妻| 久久人人爽人人爽人人片AV不| 久久久久香蕉视频| 狠狠干狠狠久久| 久久久久久久久无码精品亚洲日韩| 无码任你躁久久久久久| 韩国三级中文字幕hd久久精品 | 久久久久成人精品无码中文字幕| 国产精品成人久久久久久久| 久久精品国产免费一区| 亚洲中文字幕无码久久精品1| 久久久久亚洲AV无码专区网站| 精品无码久久久久国产| 久久精品亚洲中文字幕无码麻豆| 欧美伊人久久大香线蕉综合| 亚洲日本va午夜中文字幕久久 | 久久综合久久综合亚洲| 国产精品青草久久久久福利99 | 久久精品亚洲精品国产色婷|