• 博客访问： 1140349
• 博文数量： 196
• 博客积分： 4141
• 博客等级： 中将
• 技术积分： 2253
• 用 户 组： 普通用户
• 注册时间： 2009-03-21 20:04

2019年（31）

2016年（1）

2014年（16）

2011年（8）

2010年（25）

2009年（115）

2009-09-02 14:28:08

Jogging Trails

 Time Limit:1s Memory limit:32M Accepted Submit:56 Total Submit:144

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

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`
 ```#include #define MAX_NUM 100000000 #define MIN(x, y) (((x) < (y)) ? (x) : (y)) int nstations, ntrails; int grid[20][20]; int num; int part_result; int degree[20]; int nodes[20]; int used[20]; int search(int start, int end, int sum) {     int i;     if (start == end)     {         part_result = MIN(sum, part_result);         return 0;     }     if (used[nodes[start]] == 0)     {         used[nodes[start]] = 1;         for (i = start + 1; i < num; ++i)         {             if (used[nodes[i]] == 1)                 continue;             if (sum + grid[nodes[start]][nodes[i]] >= part_result)                 continue;             used[nodes[i]] = 1;             search(start + 1, end, sum + grid[nodes[start]][nodes[i]]);             used[nodes[i]] = 0;         }         used[nodes[start]] = 0;         return 0;     }     return search(start + 1, end, sum); } int main() {     int i, j, k;     int node0, node1, len;     int tlen;     int result;     while (scanf("%d %d", &nstations, &ntrails) == 2)     {         result = 0;         for (i = 0; i <= nstations; ++i)         {             degree[i] = 0;             used[i] = 0;             for (j = 0; j <= nstations; ++j)                 grid[i][j] = MAX_NUM;         }         for (i = 0; i < ntrails; ++i)         {             scanf("%d %d %d", &node0, &node1, &len);             result += len;             degree[node0]++;             degree[node1]++;             grid[node0][node1] = grid[node1][node0] = MIN(grid[node1][node0], len);         }         for (k = 1; k <= nstations; ++k)         {             for (i = 1; i <= nstations; ++i)             {                 for (j = 1; j <= nstations; ++j)                 {                     grid[i][j] = MIN(grid[i][j], grid[i][k] + grid[k][j]);                 }             }         }         num = 0;         for (k = 1; k <= nstations; ++k)         {             if (degree[k] & 1)                 nodes[num++] = k;         }         part_result = MAX_NUM;         search(0, num, 0);         result += part_result;         printf("%d\n", result);     }     return 0; }```