【蓝桥杯-景区导游】

题目

思路

根据题目要求，不同景点间的花费可以画成这种树

比如2 6 5 1 先求出总的花费
然后根据删去不同经典的不同的情况去计算

注意，题目已经直接给的两个直接连接景点的花费可以直接统计
间接连接的两个景点需要用dfs去搜索求出

dfs暴力代码

//暴力代码：DFS
#include<bits/stdc++.h>
#define endl '\n'
#define deb(x) cout << #x << " = " << x << '\n';
#define INF 0x3f3f3f3f
#define int long long
using namespace std;
const int N = 2e5 + 10;

typedef pair<int,int> pii;//终点  起点到终点的距离 /起点 终点  
//map<pair<int,int>, int>st;//跟下面一样的 
map<pii, int>st;//记录从{x, y}的距离是多少
int a[N];


vector<pii>edge[N];//存图

//s表示你要求的路径的起点
//v表示你要求的路径的终点
//u表示你当前走到了哪个点
//father表示你当前这个点的父亲节点是谁。避免重复走造成死循环
//sum表示从s走到u的路径花费总和。
bool dfs(int s, int u, int father, int v, int sum)
{
if(u == v)
{
st[{s, v}] = sum;
st[{v, s}] = sum;
// cout << s << " " << v << " " << sum << endl;
return true;
}

for(int i = 0; i < edge[u].size(); i ++)
{
int son = edge[u][i].first;
if(son == father)//不要来回重复走，规定方向
continue;
int w = edge[u][i].second;
if(dfs(s, son, u, v, sum + w))
return true;
}

return false;
}

void solve()
{
int n, k;
cin >> n >> k;
for(int i = 0; i < n - 1; i ++)
{
int x, y, t;
cin >> x >> y >> t;
edge[x].push_back({y, t});
edge[y].push_back({x, t});
}

for(int i = 0; i < k; i ++)
cin >> a[i];

//求出完整路线的总花费

//O(k * n)
int ans = 0;
for(int i = 0; i < k - 1; i ++)
{
dfs(a[i], a[i], -1, a[i + 1], 0);

ans += st[{a[i] ,a[i + 1]}];
}


for(int i = 0; i < k; i ++)
{
int tmp = ans;
if(i == 0)
tmp -= st[{a[i], a[i + 1]}];
else if(i == k - 1)
tmp -= st[{a[i - 1], a[i]}];
else
{
tmp -= st[{a[i - 1], a[i]}];
tmp -= st[{a[i], a[i + 1]}];
dfs(a[i - 1], a[i - 1], -1, a[i + 1], 0);
tmp += st[{a[i - 1], a[i + 1]}];
}
cout << tmp << endl;
}

}

signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
//cin >> t;
while(t--)
solve();
}

总结

这道题目的正解是书上前缀和，反正也不会，不如写个暴力解法拿一半的分。
何况其实这个暴力也不简单。

原文地址：https://blog.csdn.net/m0_63715738/article/details/137505440

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！