競賽中心 - 藍橋云課

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int A=1e5+1;
typedef pair<int,int>p;
map<p,int>st;
vector<p>edge[A];
int a[A];
int result=0;
bool dfs(int s,int u,int father,int v,int sum)
{if(u==v){st[{s,v}]=sum;st[{v,s}]=sum;return true;}for(size_t i=0;i<edge[u].size();i++){int son=edge[u][i].first;if(son==father){continue;}if(dfs(s,son,u,v,sum+edge[u][i].second)){return true;}}return false;
}
signed main()
{// 請在此輸入您的代碼int N,K,u,v,t;cin>>N>>K;for(int i=0;i<N-1;i++){cin>>u>>v>>t;edge[u].push_back({v,t});edge[v].push_back({u,t});}for(int i=0;i<K;i++){cin>>a[i];}for(int i=0;i<K-1;i++){dfs(a[i],a[i],-1,a[i+1],0);result+=st[{a[i],a[i+1]}];}for(int i=0;i<K;i++){int result1=result;if(i==0){result1-=st[{a[i],a[i+1]}];}else if(i==K-1){result1-=st[{a[i-1],a[i]}];}else{result1-=st[{a[i-1],a[i]}];result1-=st[{a[i],a[i+1]}];dfs(a[i-1],a[i-1],-1,a[i+1],0);result1+=st[{a[i-1],a[i+1]}];}cout<<result1<<" ";}return 0;
}

構造鄰接表，由于題意中存在邊權值時間，定義鄰接表為pair類型。通過typedef關鍵字重命名了pair類型為p。

根據題目要求暴力搜索題目要求的路線，得到原路線的時間總和。

dfs函數：

bool dfs(int s,int u,int father,int v,int sum)
{if(u==v){st[{s,v}]=sum;st[{v,s}]=sum;return true;}for(size_t i=0;i<edge[u].size();i++){int son=edge[u][i].first;if(son==father){continue;}if(dfs(s,son,u,v,sum+edge[u][i].second)){return true;}}return false;
}

s和v分別代表路線的起點和終點，u代表當前節點，father代表當前節點的父節點（為了防止走回頭路），sum表示起點到當前節點的路徑和。

終止條件：當當前節點到達終點，st數組存儲路徑和。

遞歸邏輯：從當前節點向后遍歷，edge[u]這個鄰接表存儲了當前節點連接的子節點，遍歷每一個子節點（注意：i的類型要為size_t，要與edge[u].size()一致）。當前節點的子節點為edge[u][i].first（表示u節點出發的第i條邊，first表示節點值，second表示邊權），如果發現子節點等于父節點，走回頭路了，就結束這次循環，換下一個節點，如果子節點可以到達目標終點，則向上返回true，如果所有條件都沒有滿足，則返回false。

問題解決思路：

for(int i=0;i<K-1;i++){dfs(a[i],a[i],-1,a[i+1],0);result+=st[{a[i],a[i+1]}];}for(int i=0;i<K;i++){int result1=result;if(i==0){result1-=st[{a[i],a[i+1]}];}else if(i==K-1){result1-=st[{a[i-1],a[i]}];}else{result1-=st[{a[i-1],a[i]}];result1-=st[{a[i],a[i+1]}];dfs(a[i-1],a[i-1],-1,a[i+1],0);result1+=st[{a[i-1],a[i+1]}];}cout<<result1<<" ";}

先暴力搜索鄰接表（a中存儲的是節點值），得到每一步的路徑值，將他們累加起來得到目標路徑總和。得到最終結果分為三種情況，第一種情況為刪掉的節點是第一個節點，就將第一個節點和第二個節點的路徑減去就解決了。第二種情況是刪掉的節點是最后一個節點，就將最后一個節點和倒數第二個節點的路徑減去就解決了。第三種情況為其他，減去左右兩節點的路徑和后還要加上左節點到右節點的路徑和，這個路徑和并沒有搜索過，所以要再進行一遍搜索。