FZU 1009 Jogging Trails 最短路+歐拉回路 解題報告

Problem 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 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 andn, 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.

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

Sample Input

4 51 2 32 3 43 4 51 4 101 3 120

Sample Output

41 

題意：它讓我們經過每條邊至少一次，然後回到原點，求可以達到要求的最短的總路徑。

是以，這個路徑為歐拉回路，歐拉回路要求所有點的入度為偶數。

由于n<15，是以用dis[111111111]來記錄狀态，1為偶，0為奇。

代碼（模仿大神代碼寫的，原文）：

#include <cstdio>
#include <queue>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;

const int maxn = 15+1;
const int maxm = 1<<maxn;
struct Node
{
    int pos;//目前的狀态
    int dist;//目前狀态的距離
    Node(int pos,int dist)
    {
        this->pos = pos;
        this->dist = dist;
    }
    //重載小于運算符
    bool operator<(const struct Node &ans)const
    {
        return dist > ans.dist;
    }
};

int degree[maxn],edge[maxn][maxn],dis[maxm];
bool vis[maxm];
int n, m, st, ed, sum;

void dijkstra()
{
    priority_queue<Node> Q;
    int up = 1 << n;
    for(int i = 0; i< up;i++)
    {
        dis[i] = -1;
        vis[i] = false;
    }
    dis[st] = sum;
    Q.push(Node(st,dis[st]));
    while(!Q.empty())
    {
        Node ans = Q.top();
        Q.pop();
        int u = ans.pos;
        if(vis[u]) continue;
        vis[u] = true;
        if(u == ed) break;
        for(int i = 0; i <n; i++)
        {
            for(int j = 0;j < i; j++)
            {
                if(edge[i][j] != -1)
                {
                    int v = u ^ (1<<i);
                    v = v ^ (1<<j);
                    if(dis[v] == -1 || dis[u] + edge[i][j] < dis[v])
                    {
                        dis[v] = dis[u] + edge[i][j];
                        Q.push(Node(v, dis[v]));
                    }
                }
            }
        }
    }
}

int main()
{
    while(scanf("%d", &n)!=EOF, n)
    {
        scanf("%d", &m);
        for(int i = 0; i < n; i++)
        {
            degree[i] = 0;
            for(int j = 0; j < n; j++)
                edge[i][j] = -1;
        }
        int a,b,c;
        sum = 0;
        for(int i = 0;i < m; i++)
        {
            scanf("%d%d%d", &a, &b, &c);
            a--,b--;
            degree[a]++;
            degree[b]++;
            sum += c;
            if(edge[a][b] == -1 || edge[a][b] > c)
                edge[a][b] = edge[b][a] = c;
        }
        st = ed = 0;
        for(int i = 0; i < n; i++)
        {
            ed |= (1 << i);
            if(degree[i] % 2 == 0)
                st |= (1 << i);
        }
        dijkstra();
        printf("%d\n", dis[ed]);
    }
    return 0;
}