• <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>
            Jogging Trails
            Time Limit: 1000MS
            Memory Limit: 65536K
            Total Submissions: 1710
            Accepted: 672

            Description

            Gord is training for a marathon. Behind his house is a park with a large network of jogging trails connecting water stations. Gord wants to find the shortest jogging route that travels along every trail at least once.

            Input

            Input consists of several test cases. The first line of input for each case contains two positive integers: n <= 15, the number of water stations, and m < 1000, the number of trails. For each trail, there is one subsequent line of input containing three positive integers: the first two, between 1 and n, indicating the water stations at the end points of the trail; the third indicates the length of the trail, in cubits. There may be more than one trail between any two stations; each different trail is given only once in the input; each trail can be travelled in either direction. It is possible to reach any trail from any other trail by visiting a sequence of water stations connected by trails. Gord's route may start at any water station, and must end at the same station. A single line containing 0 follows the last test case.

            Output

            For each case, there should be one line of output giving the length of Gord's jogging route.

            Sample Input

            4 5 1 2 3 2 3 4 3 4 5 1 4 10 1 3 12 0 

            Sample Output

            41 

            Source

            Waterloo local 2002.07.01

            今天在毛哥的幫助下加深了對此題的理解,題目要求的其實是構造一個歐拉回路,那么:每次加邊,改變兩個奇數點的奇偶性,直到全為偶

            #include<cstdio>
            #include
            <cstring>
            #include
            <iostream>
            using namespace std;
            const int MAXN = 30;
            const int inf = 999999999;
            int dp[1<<15];
            int deg[MAXN],e[MAXN][MAXN];
            void floyd(int n){
                
            for(int k=0;k<n;k++)
                    
            for(int i=0;i<n;i++)
                        
            for(int j=0;j<n;j++)
                            e[i][j]
            =min(e[i][j],e[i][k]+e[k][j]);
            }
            int dfs(int s,int n){
                
            if(!s) return 0;
                
            if(dp[s]>0return dp[s];
                dp[s]
            =inf;
                
            for(int i=0;i<n;i++)
                    
            if(s|(1<<i))
                        
            for(int j=i+1;j<n;j++)
                            
            if(s|(1<<j)){
                                
            int tmp=dfs(s^(1<<i)^(1<<j),n)+e[i][j];
                                
            if(dp[s]>tmp) dp[s]=tmp;
                            }
                
            return dp[s];
            }
            int main(){
                
            int n,m,ans,s,u,v,w;
                
            while(~scanf("%d%d",&n,&m) && n){
                    
            for(int i=0;i<n;i++)
                        
            for(int j=0;j<n;j++)
                            e[i][j]
            =inf;
                    
            for(int i=0;i<n;i++) deg[i]=0;
                    ans
            =0;
                    
            while(m--){
                        scanf(
            "%d%d%d",&u,&v,&w);
                        u
            --;v--;
                        
            if(e[u][v]>w) e[u][v]=e[v][u]=w;
                        ans
            +=w;deg[u]++;deg[v]++;
                    }
                    s
            =0;
                    
            for(int i=0;i<n;i++if(deg[i]%2) s|=(1<<i);
                    memset(dp,
            -1,sizeof(dp));
                    ans
            +=dfs(s,n);
                    printf(
            "%d\n",ans);
                }
                
            return 0;
            }

            posts - 3, comments - 1, trackbacks - 0, articles - 16

            Copyright © lenohoo

            国产V亚洲V天堂无码久久久| 人妻中文久久久久| 久久久久亚洲AV片无码下载蜜桃| 亚洲精品乱码久久久久久久久久久久| 亚洲精品tv久久久久久久久| 久久九九青青国产精品| 久久亚洲天堂| 亚洲中文字幕无码一久久区| 亚洲国产成人久久精品影视| 精品久久久久久中文字幕大豆网| 久久久久一区二区三区| 武侠古典久久婷婷狼人伊人| 99精品久久久久中文字幕| 亚洲国产精品无码久久久久久曰| 久久久精品人妻一区二区三区四| 久久精品国产一区二区三区| 精品熟女少妇a∨免费久久| 日日狠狠久久偷偷色综合免费| 久久精品国产亚洲av高清漫画| 日本亚洲色大成网站WWW久久| 国产成年无码久久久久毛片| 久久久久亚洲精品日久生情| 亚洲一区二区三区日本久久九| 亚洲av日韩精品久久久久久a| 久久精品亚洲福利| 精品久久久久久无码免费| 国产精品久久毛片完整版| 久久精品亚洲一区二区三区浴池| 一本综合久久国产二区| 色偷偷88欧美精品久久久| 99热都是精品久久久久久| 精品999久久久久久中文字幕| 久久精品国产亚洲AV高清热| A级毛片无码久久精品免费| 亚洲欧美一区二区三区久久| 久久久无码精品午夜| 久久久久亚洲精品天堂久久久久久 | 久久精品国产99久久久古代| 久久有码中文字幕| 久久性精品| 欧美伊人久久大香线蕉综合|