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