2010年02月28日星期日.sgu145
sgu145:dfs + 二分
話說這個思路是看別人的思路看來的，我就想A*啥的了，結(jié)果才發(fā)現(xiàn)是不重復(fù)的第k最短路。
沒有發(fā)現(xiàn)還能這么搞。
二分第k長路的值，然后搜有多少條路的值小于等于k。這樣能得到一個第k條最短路的值，然后再搜一次，
把這個值輸出出來即可。
關(guān)鍵是這個思路不好想，代碼的話，注意搜有多少條路小于等于k時剪枝優(yōu)化。
?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.shnenglu.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?