解題思路： 先我們考慮從源點出發到所有自己想要經過的點然后在回到源點sum，顯然每條邊都必須經過源點（這個我們可以一次dfs求出），但題目的意思是可以不用回到源點，那么我們可以再求源點到所有要經過的點的最遠距離ans,于是答案便是sum-ans.

這道題的思路確實是很巧妙，一開始我還是在想如何表示從某一點回來的狀態，數據太大用狀態壓縮肯定不行，結果就沒思路了，看了別人的思路確實是抓住了這道題的精髓。。。

#include<iostream> #include<cstdio> #include<cstring> using namespace std;const int maxn = 50005; struct Edge {int w,v,next; }edge[maxn<<1]; int n,m,k,pre[maxn],dis[maxn],cnt,sum; bool vis[maxn];void addedge(int u,int v,int w) {edge[cnt].v = v;edge[cnt].w = w;edge[cnt].next = pre[u];pre[u] = cnt++; }void dfs(int u,int f) {for(int i = pre[u]; i != -1; i = edge[i].next){int v = edge[i].v, w = edge[i].w;if(v == f) continue;dis[v] = dis[u] + w;dfs(v,u);if(vis[v]){sum += 2*w;vis[u] = true;}} }int main() {while(scanf("%d%d",&n,&k)!=EOF){cnt = 0;memset(pre,-1,sizeof(pre));memset(vis,false,sizeof(vis));for(int i = 1; i < n; i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);addedge(u,v,w);addedge(v,u,w);}scanf("%d",&m);while(m--){int u;scanf("%d",&u);vis[u] = true;}sum = 0; dis[k] = 0; m = 0;dfs(k,-1);for(int i = 1; i <= n; i++){if(vis[i] == false) continue;m = max(m,dis[i]);}printf("%d\n",sum - m);}return 0; }

總結

以上是生活随笔為你收集整理的poj 1935(搜索+回溯)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。