題干：

鏈接：https://ac.nowcoder.com/acm/contest/188/C
來源：牛客網
?

小w不會離散數學，所以她van的圖論游戲是送分的

小w有一張n個點n-1條邊的無向聯通圖,每個點編號為1~n,每條邊都有一個長度
小w現在在點x上
她想知道從點x出發經過每個點至少一次，最少需要走多少路

輸入描述:

第一行兩個整數 n,x,代表點數,和小w所處的位置 第二到第n行,每行三個整數 u,v,w,表示u和v之間有一條長為w的道路

輸出描述:

一個數表示答案

示例1

輸入

復制

3 1 1 2 1 2 3 1

輸出

復制

2

備注:

1 ≤ n ≤ 50000 , 1 ≤ w ≤ 2147483647

解題報告：

? 和? ?牛客369的C一樣的思維。

AC代碼：

#include <queue> #include <cstdio> #include <cstring> #include <iostream> #define ll long long using namespace std; const int MAX = 6e5 + 5 ; const int INF = 0x3f3f3f3f; struct Node {int to;int w;int ne; } e[MAX]; struct point {int pos,c;point(){}point(int pos,int c):pos(pos),c(c){}}; int n; int head[MAX]; int cnt = 0 ; bool vis[MAX]; void init() {cnt = 0;memset(head,-1,sizeof(head)); } void add(int u,int v,int w) {e[cnt].to = v;e[cnt].w = w;e[cnt].ne = head[u];head[u] = cnt;cnt++; } int bfs(int x,int &w) {queue <point> q;int maxx = 0;int retp = x ;//返回的點坐標 memset(vis,0,sizeof(vis) );q.push(point(x,0));vis[x] = 1;point now;while(q.size() ) {point cur = q.front();q.pop();for(int i = head[cur.pos]; i!=-1; i=e[i].ne) {if(vis[e[i].to]) continue;vis[e[i].to] = 1;now.pos = e[i].to;now.c = cur.c + e[i].w;if(now.c>maxx) {maxx = now.c;retp = now.pos;}q.push(now);}//w = maxx;}w = maxx;return retp; } int main() {int x;cin>>n>>x;init();int u,v,w;ll sum = 0;for(int i = 1; i<=n-1; i++) {scanf("%d%d%d",&u,&v,&w);add(u,v,w);add(v,u,w);sum += w;}int ans1 = 0,ans2 = 0;u = bfs(x,ans1);//printf("ans2 = %d\n",ans2);printf("%lld\n",1LL*ans1 + (sum-ans1)*2);return 0 ; }

?

總結

以上是生活随笔為你收集整理的【牛客 - 188C】水图（bfs树的直径，思维）的全部內容，希望文章能夠幫你解決所遇到的問題。

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