最小斯泰纳树，直接用吉大模板
1 /*
2 * File: HNU 10862 Ticket to Ride
3 * Author: xiaotian @ hnu
4 * Created on 2010年10月6日, 下午7:48
5 * 题解：最小斯泰纳树，直接套板
6 */
7
8 #include<stdio.h>
9 #include<iostream>
10 #include<string>
11 #include<queue>
12 #include<map>
13 #include<set>
14 #include<math.h>
15 using namespace std;
16 #define N 1000
17 #define A 8
18 #define inf 0x7ffffff
19 int vis[N], id[A]; //id[]: A中点的标号
20 int d[N][N], dp[1 << A][N]; //dp[i][v]: 点v到点集i的最短距离
21 map<string, int>mp, fg;
22
23 int min(int a, int b) {
24 return a < b ? a : b;
25 }
26
27 void steiner(int n, int a) {
28 int i, j, k, mx, mk, top = (1 << a);
29 for (k = 0; k < n; k++)
30 for (i = 0; i < n; i++)
31 for (j = 0; j < n; j++)
32 if (d[i][j] > d[i][k] + d[k][j])
33 d[i][j] = d[i][k] + d[k][j];
34 for (i = 0; i < a; i++) { // vertex: 0 ~ n-1
35 for (j = 0; j < n; j++)
36 dp[1 << i][j] = d[j][ id[i] ];
37 }
38 for (i = 1; i < top; i++) {
39 if (0 == (i & (i - 1))) continue;
40 memset(vis, 0, sizeof (vis));
41 for (k = 0; k < n; k++) { // init
42 for (dp[i][k] = inf, j = 1; j < i; j++)
43 if ((i | j) == i &&
44 dp[i][k] > dp[j][k] + dp[i - j][k])
45 dp[i][k] = dp[j][k] + dp[i - j][k];
46 }
47 for (j = 0; mx = inf, j < n; j++) { // update
48 for (k = 0; k < n; k++)
49 if (dp[i][k] <= mx && 0 == vis[k])
50 mx = dp[i][mk = k];
51 for (k = 0, vis[mk] = 1; k < n; k++)
52 if (dp[i][mk] > dp[i][k] + d[k][mk])
53 dp[i][mk] = dp[i][k] + d[k][mk];
54 }
55 }
56 }
57
58 int main() {
59 int n, m, a = 8, w;
60 char s1[25], s2[25];
61 while (scanf("%d%d\n", &n, &m) != EOF) {
62 if (n == 0 && m == 0) return 0;
63 mp.clear();
64 for (int i = 0; i < n; i++) {
65 scanf("%s",s1);
66 mp[s1] = i + 1;
67 }
68 for (int i = 0; i <= n; i++)
69 for (int j = 0; j <= n; j++) d[i][j] = i==j?0:inf;
70 for (int i = 0; i < m; i++) {
71 scanf("%s %s %d", s1, s2, &w);
72 int u = mp[s1] - 1;
73 int v = mp[s2] - 1;
74 d[u][v] = d[v][u] = min(d[u][v], w);
75 }
76 fg.clear();
77 for (int i = 0; i < 8; i++) {
78 scanf("%s", s1);
79 id[i] = mp[s1] - 1;
80 }
81 steiner(n, a);
82 int i, j, z, x, y, k, b;
83 for (i = 0, b = inf; z = 0, i < 256; b > z ? b = z : b, i++)
84 for (j = 0; y = 0, j < 4; z += !!y * dp[y][x], j++)
85 for (k = 0; k < 8; k += 2)
86 if ((i >> k & 3) == j)
87 y += 3 << k, x = id[k];
88 printf("%d\n",b);
89 }
90 }