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

            7777精品伊人久久久大香线蕉| 少妇精品久久久一区二区三区 | 人妻无码久久精品| 国产精品gz久久久| 麻豆精品久久久久久久99蜜桃| 亚洲欧美日韩中文久久| 91久久婷婷国产综合精品青草| 久久久精品免费国产四虎| 久久精品夜色噜噜亚洲A∨| 久久久久免费精品国产| 99国产欧美久久久精品蜜芽 | 免费一级做a爰片久久毛片潮| 超级碰碰碰碰97久久久久| 久久综合九色综合网站| 99久久免费只有精品国产| 久久婷婷五月综合成人D啪| 久久99精品综合国产首页| 女同久久| 99久久综合狠狠综合久久止| 亚洲国产精品综合久久网络 | 久久精品免费一区二区| 国产精品成人无码久久久久久 | 色综合久久中文综合网| 狠狠色婷婷久久综合频道日韩 | 2020久久精品亚洲热综合一本| 精品九九久久国内精品| 亚洲国产精品成人久久| 亚洲国产成人久久笫一页| 国产精品美女久久久久AV福利| 久久精品国产亚洲精品2020| 久久天天躁夜夜躁狠狠| 三级片免费观看久久| 久久www免费人成看国产片| 久久99国产精品久久| 看久久久久久a级毛片| 国产69精品久久久久久人妻精品| 久久久噜噜噜久久| 亚洲国产精品成人久久蜜臀| 亚洲人成无码网站久久99热国产| 久久久WWW免费人成精品| 久久精品一区二区三区中文字幕|