Morris' Blog 我在摸索我存在的意、生命的意、涵及值。 有真正神手般的害，套用模式是大部分的情。 那害的我存在的意何，托出神的存在？ 有候不能怪人不我，我已始省思， 什我有人的原因，而是全要靠人。 有候我我不同，那是因我做不到很多人能到的事情。 我不到、玩不起、得不明、理解得不多， 我缺少的文能力，就是一切一切能的判定。 此，我不得能做些人有助的事情。 我知道我自己是不服的性格，但在我不得不。 我有能力，因此我必。 我到底世界作什？充不定性， 而我是法出拔萃，想一般人似乎也回不了了。 越大的挑需要越力的支持，而我的支持是什？ 最近人，但都是失的局，人能接受， 不需要言，不需要通，一切所想都表不出。

49的鼓 6站台

Problem B: Jogging Trails

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 5 1 2 3 2 3 4 3 4 5 1 4 10 1 3 12 0 

Output for Sample Input

41

#include <stdio.h>
#include <string.h>
#define min(x, y) ((x) < (y) ? (x) : (y))
int map[16][16], odd[16];
void floyd(int n) {
 int i, j, k;
 for(k = 1; k <= n; k++)
 for(i = 1; i <= n; i++)
 for(j = 1; j <= n; j++)
 map[i][j] = min(map[i][j], map[i][k]+map[k][j]);
}
int dp[1<<16];
int build(int pN, int ot) {
 if(pN == 0)
 return 0;
 if(dp[pN] != -1)
 return dp[pN];
 int i, j, tmp;
 dp[pN] = 0xfffffff;
 for(i = 0; i < ot; i++) {
 if(pN&(1<<i)) {
 for(j = i+1; j < ot; j++) {
 if(pN&(1<<j)) {
 tmp = build(pN-(1<<i)-(1<<j), ot);
 dp[pN] = min(dp[pN], tmp+map[odd[i]][odd[j]]);
 }
 }
 break;
 }
 }
 return dp[pN];
}
int main() {
 int n, m, x, y, w;
 while(scanf("%d", &n) == 1 && n) {
 scanf("%d", &m);
 memset(map, 63, sizeof(map));
 memset(dp, -1, sizeof(dp));
 int sum = 0, deg[16] = {};
 while(m--) {
 scanf("%d %d %d", &x, &y, &w);
 map[x][y] = min(map[x][y], w);
 map[y][x] = min(map[y][x], w);
 deg[x]++, deg[y]++;
 sum += w;
 }
 floyd(n);
 int ot = 0;
 for(int i = 1; i <= n; i++)
 if(deg[i]&1)
 odd[ot++] = i;
 printf("%d\n", sum+build((1<<ot)-1, ot));
 }
 return 0;
}
 

您可能以下文章有趣

[UVA][Easy] 12626 - I Pizza

[UVA][] 11648 - Divide The Land

[UVA][Trie] 11286 - Conformity

[UVA][priority_queue] 11926 - Multitasking