題目描述

?

? ? 給出一個n個點m條邊的無向圖，n個點的編號從1~n，定義源點為1。定義最短路樹如下：從源點1經(jīng)過邊集T到任意一點i有且僅有一條路徑，且這條路徑是整個圖1到i的最短路徑，邊集T構(gòu)成最短路樹。

???給出最短路樹，求對于除了源點1外的每個點i，求最短路，要求不經(jīng)過給出的最短路樹上的1到i的路徑的最后一條邊。

?

輸入

?

? ?第一行包含兩個數(shù)n和m，表示圖中有n個點和m條邊。

???接下來m行，每行有四個數(shù)ai，bi，li，ti，表示圖中第i條邊連接ai和bi權(quán)值為li，ti為1表示這條邊是最短路樹上的邊，ti為0表示不是最短路樹上的邊。

?

輸出

?

輸出n-1個數(shù)，第i個數(shù)表示從1到i+1的要求的最短路。無法到達(dá)輸出-1。

?

樣例輸入

5 9 3 1 3 1 1 4 2 1 2 1 6 0 2 3 4 0 5 2 3 0 3 2 2 1 5 3 1 1 3 5 2 0 4 5 4 0

樣例輸出

6 7 8 5

提示

?

對于30%的數(shù)據(jù)，n≤100，m≤2000
對于100%的數(shù)據(jù)，n≤4000，m≤100000，1≤li≤100000

?

分析：

考慮一個點的答案是怎么樣的：從$1$到$i$的答案，應(yīng)該是從$1$沿著樹邊走，然后經(jīng)過一條非樹邊走到以$i$為根的子樹中，在沿著樹邊向上走到$i$。畫圖可以證明走兩條非樹邊一定更不優(yōu)。$p[i][j]$表示$i->j$的只經(jīng)過一條兩端在$i$和$j$的子樹非樹邊最短路，$dis[i]$表示$1->i$的最短路，所以$ans[i]=min（p[x][i]+dis[x]）$，$x$是$i$子樹中的一點。

那么只要處理$dis[i]$和$p[i][j]$，$dis[i]$只要求樹上距離即可，$p[i][j]$的計算類似更新答案，$dfs$過程中枚舉$1~n$個點，然后用用兒子節(jié)點更新當(dāng)前節(jié)點即可。

#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #define M 200005 #define N 4005 using namespace std; int n,m,dis[N],p[N][N],ans[N],pre[N],las[N],ind; int hd[N],to[M],nx[M],w[M],cnt; inline void add(int u,int v,int c){to[++cnt]=v;w[cnt]=c;nx[cnt]=hd[u];hd[u]=cnt; } inline void dfs1(int u,int f){pre[u]=++ind;for(int i=hd[u];i;i=nx[i]){int v=to[i];if(v!=f){dis[v]=dis[u]+w[i];dfs1(v,u);}}las[u]=ind; } inline void dfs2(int u,int f){for(int i=hd[u];i;i=nx[i]){int v=to[i];if(v!=f){dfs2(v,u);for(int j=1;j<=n;j++){if(pre[j]>=pre[u]&&las[j]<=las[u]) continue;p[u][j]=min(p[u][j],p[v][j]+w[i]);}}}for(int i=1;i<=n;i++){if(pre[i]>=pre[u]&&las[i]<=las[u]) continue;ans[u]=min(ans[u],p[u][i]+dis[i]);} } int main(){scanf("%d%d",&n,&m);memset(p,123,sizeof p);for(int i=1;i<=m;i++){int a,b,l,t;scanf("%d%d%d%d",&a,&b,&l,&t);if(t){add(a,b,l);add(b,a,l);}else p[a][b]=p[b][a]=min(p[a][b],l);}memset(ans,123,sizeof ans);dfs1(1,0);dfs2(1,0);for(int i=2;i<=n;i++)if(ans[i]==ans[0]) puts("-1");else printf("%d\n",ans[i]);return 0; }

總結(jié)：

圖論等，尤其是圖論題。很多時候要考慮答案長什么樣，什么情況下最優(yōu)，當(dāng)有了特殊性質(zhì)時，題目會更好做。

如果要證明一些性質(zhì)，可以先假設(shè)一些條件，然后用反證法。例如：假設(shè)最優(yōu)答案在(……)上，如果有更優(yōu)的答案，那么(……)就不是(……)。之類的……

?

轉(zhuǎn)載于:https://www.cnblogs.com/ssoiRoor/p/9917163.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ 3694DTOJ 1972: 最短路的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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