Description

8102年，Normalgod在GLaDOS的幫助下，研制出了傳送槍。但GLaDOS想把傳送槍據(jù)為己有，于是把Normalgod扔進了一間實驗室。這間實驗室是一棵有n個節(jié)點的樹。現(xiàn)在Normalgod在一號節(jié)點，出口也在一號節(jié)點，但為了打開它，必須經(jīng)過每一個節(jié)點按下每個節(jié)點的開關(guān)，出口才能打開。GLaDOS為了殺死Normalgod，開始在實驗室里釋放毒氣，因此Normalgod必須盡快逃出這間實驗室。
當(dāng)然，Normalgod手中的傳送槍是可以使用的。傳送槍可以發(fā)射出兩個顏色不同的傳送門。Normalgod可以從其中一個傳送到另一個。盡管傳送槍可以在視野范圍內(nèi)的任何一個經(jīng)過特殊處理的表面打開一扇傳送門，但這間實驗室的設(shè)計使得Normalgod只能在他所處的房間內(nèi)打開一個傳送門。 在已經(jīng)存在了一個同顏色的傳送門時，打開新的傳送門會使與它同顏色的舊門消失。傳送和打開傳送門所需時間為0。
顯然，利用傳送槍會讓Normalgod更快解決謎題，可Normalgod死在了按下最后一個按鈕的路上。盡管如此，GLaDOS還是很想知道到底Normalgod最快能用多久逃出去，這對她的實驗室設(shè)計方法論有重要的指導(dǎo)作用。作為GLaDOS的算法模塊，你要完成這個任務(wù)。本題時限為2000ms

Input

第一行一個整數(shù)n。之后n-1行，每行三個整數(shù)ui，vi，ai ,表示有一條從ui 連向vi ，花費時間為ai 的通道。

Output

一行一個數(shù)T，表示最小的脫逃時間。

Sample Input

5
1 2 2
2 3 3
2 4 5
1 5 1

Sample Output

13

樣例說明
1–> open1–> 5–> open2–> use(1)–> 2–> 3–> open2–> use(1)–> 2–> 4–> open2–> use(1)–> exit

Data Constraint

Solution

• 我們發(fā)現(xiàn)每條邊至少會被走過一次，而最多被走過兩次。

• 且在一個子樹尚未遍歷完的情況下不會突然跑去別的子樹。

• 于是考慮樹形DP，設(shè) $f[x]$ 表示以 $x$ 為根的子樹遍歷完回到 $x$ 的最小時間。

• 如果在 $x$ 點不開傳送門，那么就可從其兒子 $y$ （之間的邊權(quán)值為 $v$）累加來;

• 如果在 $x$ 點開傳送門，則在 $y$ 子樹中不斷走，在某一點傳回 $x$ ，

• 顯然該點為 $y$ 子樹中的最長鏈（長度設(shè)為 $len[y]$）。

• 且 $y$ 子樹中其他的每條邊都會走兩遍（子樹邊權(quán)和設(shè)為 $sum[y]$）。

• 轉(zhuǎn)移方程即為：$$f[x]+=min(f[y]+v?2,sum[y]?2?len[y]+v)$$

Code

#include<cstdio> #include<cctype> using namespace std; typedef long long LL; const int N=1e6+5; int tot; int first[N],nex[N<<1],en[N<<1],w[N<<1]; LL len[N],f[N],sum[N]; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } inline LL max(LL x,LL y) {return x>y?x:y; } inline LL min(LL x,LL y) {return x<y?x:y; } inline void insert(int x,int y,int z) {nex[++tot]=first[x];first[x]=tot;en[tot]=y;w[tot]=z; } void dfs(int x,int y) {for(int i=first[x];i;i=nex[i])if(en[i]^y){dfs(en[i],x);len[x]=max(len[x],len[en[i]]+w[i]);sum[x]+=sum[en[i]]+w[i];f[x]+=min(f[en[i]]+w[i]*2,sum[en[i]]*2-len[en[i]]+w[i]);} } int main() {freopen("portal.in","r",stdin);freopen("portal.out","w",stdout);int n=read();for(int i=1;i<n;i++){int x=read(),y=read(),z=read();insert(x,y,z);insert(y,x,z);}dfs(1,0);printf("%lld",f[1]);return 0; } 與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的JZOJ 5906. 【NOIP2018模拟10.15】传送门 （portal）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。