• <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 已經(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
            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

            日本强好片久久久久久AAA| 久久久精品一区二区三区| 人妻无码久久精品| 色妞色综合久久夜夜| 亚洲狠狠久久综合一区77777| 国产91久久综合| 久久久久久综合网天天| 久久精品国产91久久麻豆自制| 看全色黄大色大片免费久久久 | 伊人久久大香线蕉影院95| 一本久久久久久久| 久久久一本精品99久久精品88| 国产一久久香蕉国产线看观看| 亚洲欧美久久久久9999| 国产精品禁18久久久夂久| 看全色黄大色大片免费久久久 | 亚洲精品美女久久久久99| 国产精品伊人久久伊人电影| 亚洲午夜久久久影院伊人| 久久精品国产精品亜洲毛片| 国产欧美久久一区二区| 精品人妻伦九区久久AAA片69| 狠狠综合久久综合中文88 | 热99re久久国超精品首页| 久久热这里只有精品在线观看| 国产ww久久久久久久久久| 国产成人精品久久免费动漫| 亚洲午夜久久久影院伊人| 久久久综合香蕉尹人综合网| 色综合久久88色综合天天| 亚洲人成伊人成综合网久久久| 综合久久一区二区三区 | 精品久久久久久无码专区不卡 | 中文字幕乱码久久午夜| 亚洲精品无码久久久| 青青草国产97免久久费观看| 国产精品免费久久久久久久久| 久久美女网站免费| 国产高潮久久免费观看| 久久精品无码一区二区三区日韩| 国产精品女同一区二区久久|