• <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

            久久99热这里只有精品国产| 精品久久久久久无码中文野结衣 | 久久亚洲日韩看片无码| 色综合久久久久综合99| 亚洲精品美女久久777777| 99久久国产综合精品麻豆| 国产精品99久久久久久www| 久久久久亚洲av综合波多野结衣| 国内精品久久久久久99| 四虎国产精品成人免费久久| 精品国产VA久久久久久久冰 | 久久久久亚洲av无码专区| 99久久人人爽亚洲精品美女| 少妇熟女久久综合网色欲| 久久最近最新中文字幕大全| 久久乐国产综合亚洲精品| 91精品日韩人妻无码久久不卡| 国产毛片欧美毛片久久久| 久久综合久久综合久久| 久久国产热精品波多野结衣AV| 中文字幕久久亚洲一区| 久久九色综合九色99伊人| 久久99精品国产| 激情伊人五月天久久综合| 狠狠精品久久久无码中文字幕| 看全色黄大色大片免费久久久| 99精品伊人久久久大香线蕉| 久久久久久亚洲Av无码精品专口 | 韩国无遮挡三级久久| 久久永久免费人妻精品下载| 国产精品久久婷婷六月丁香| 久久国产免费| 久久夜色撩人精品国产| 久久97久久97精品免视看秋霞 | 精品久久一区二区| 久久91精品国产91久久户| 国产精品久久亚洲不卡动漫| 国产高潮国产高潮久久久| 97精品伊人久久大香线蕉app| av无码久久久久不卡免费网站 | 91精品观看91久久久久久 |