图论（邻接表）DFS

竞赛中心 - 蓝桥云课

#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中存储的是节点值），得到每一步的路径值，将他们累加起来得到目标路径总和。得到最终结果分为三种情况，第一种情况为删掉的节点是第一个节点，就将第一个节点和第二个节点的路径减去就解决了。第二种情况是删掉的节点是最后一个节点，就将最后一个节点和倒数第二个节点的路径减去就解决了。第三种情况为其他，减去左右两节点的路径和后还要加上左节点到右节点的路径和，这个路径和并没有搜索过，所以要再进行一遍搜索。