2010年02月28日星期日.sgu145
sgu145:dfs + 二分
话说这个思路是看别人的思路看来的，我就想A*啥的了，结果才发现是不重复的第k最短路。
没有发现还能这么搞。
二分第k长路的值，然后搜有多少条路的值小于等于k。这样能得到一个第k条最短路的值，然后再搜一次，
把这个值输出出来即可。
关键是这个思路不好想，代码的话，注意搜有多少条路小于等于k时剪枝优化。
1
2 const int N = 128;
3 int src, des, n, m, K, vis[N], cnt, mid;
4 vector < int >g[N];
5 #define pb(x) push_back(x)
6
7 void dfs(int u, int cost)
8 {
9 if (u == des) {
10 if (cost <= mid) {
11 cnt++;
12 }
13 return;
14 }
15
16 int sz = g[u].size();
17 for (int i = 0; i < sz; i += 2) {
18 int v = g[u][i];
19 int w = g[u][i + 1];
20 if (!vis[v] && cost + w <= mid) {
21 vis[v] = true;
22 dfs(v, cost + w);
23 vis[v] = false;
24 }
25 if (cnt >= K) { //pruning
26 return;
27 }
28 }
29 }
30//http://www.cppblog.com/schindlerlee
31 void pathcnt()
32 {
33 memset(vis, 0, sizeof(vis)), cnt = 0;
34 vis[src] = true;
35 dfs(src, 0);
36 }
37
38 int out[N],top,ans;
39 bool dfs2(int u, int cost)
40 {
41 if (u == des) {
42 if (cost == ans) {
43 out[top++] = u;
44 return true;
45 }
46 return false;
47 }
48
49 int sz = g[u].size();
50 for (int i = 0; i < sz; i += 2) {
51 int v = g[u][i];
52 int w = g[u][i + 1];
53 if (!vis[v] && cost + w <= ans) {
54 vis[v] = true;
55 if (dfs2(v, cost + w)) {
56 out[top++] = u;
57 return true;
58 }
59 vis[v] = false;
60 }
61 }
62 return false;
63 }
64
65
66 int main()
67 {
68 int i, j, a, b, c;
69 scanf("%d%d%d", &n, &m, &K);
70 for (i = 0; i < m; i++) {
71 scanf("%d %d %d", &a, &b, &c);
72 g[a].pb(b), g[a].pb(c);
73 g[b].pb(a), g[b].pb(c);
74 }
75
76 scanf("%d%d", &src, &des);
77 int left = 1, right = 1000001;
78 while (left < right) {
79 mid = (left + right) >> 1;
80 pathcnt();
81 if (cnt < K) {
82 left = mid + 1;
83 } else {
84 right = mid;
85 }
86 }
87 ans = left;
88 memset(vis,0,sizeof(vis)), vis[src] = true;
89 assert(dfs2(src,0));
90 printf("%d %d\n",ans,top);
91 for (i = top - 1;i >= 0;i --) {
92 printf("%d ",out[i]);
93 }
94 printf("\n");
95 return 0;
96 }
97