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

            久久永久免费人妻精品下载| 热久久这里只有精品| 国产99久久九九精品无码| 97久久精品人人澡人人爽| 少妇人妻综合久久中文字幕| 色婷婷久久综合中文久久蜜桃av| 久久久一本精品99久久精品66| 国产精品九九久久免费视频| 国内精品伊人久久久久网站| 亚洲国产精品无码久久久不卡| 国内精品久久久久久久久电影网| 亚洲国产成人久久综合野外| 99久久婷婷国产一区二区| 亚洲欧美久久久久9999| 日本久久久久久中文字幕| 国产成人精品三上悠亚久久| 久久精品视频91| 88久久精品无码一区二区毛片 | 久久久久亚洲Av无码专| 精品久久久久久国产免费了| 久久男人Av资源网站无码软件| 久久久精品人妻无码专区不卡 | 久久强奷乱码老熟女网站| 国产精品久久久久久| 久久不见久久见免费视频7| 欧美午夜A∨大片久久 | 18岁日韩内射颜射午夜久久成人 | 久久久久久久久久久久中文字幕| 久久久久久久综合日本| 97久久精品人人澡人人爽| 久久国产亚洲高清观看| 亚洲综合熟女久久久30p| 亚洲中文字幕久久精品无码喷水| 亚洲国产视频久久| 久久精品国产AV一区二区三区 | 久久综合狠狠综合久久激情 | 久久国产乱子伦免费精品| 国产亚洲精品美女久久久| 精品无码久久久久久国产| 国产精品成人99久久久久91gav| 久久综合综合久久狠狠狠97色88|