Gremlins最近在農(nóng)場(chǎng)上泛濫,它們經(jīng)常會(huì)阻止牛們從農(nóng)莊(牛棚_1)走到別的牛棚(牛_i的目的 地是牛棚_i).每一個(gè)gremlin只認(rèn)識(shí)牛_i并且知道牛_i一般走到牛棚_i的最短路經(jīng).所以它 們?cè)谂i到牛棚_i之前的最后一條牛路上等牛_i. 當(dāng)然,牛不愿意遇到Gremlins,所以準(zhǔn)備找 一條稍微不同的路經(jīng)從牛棚_1走到牛棚_i.所以,請(qǐng)你為每一頭牛_i找出避免gremlin_i的最 短路經(jīng)的長度.和以往一樣, 農(nóng)場(chǎng)上的M (2 <= M <= 200,000)條雙向牛路編號(hào)為1..M并且能讓所有牛到 達(dá)它們的目的地, N(3 <= N <= 100,000)個(gè)編號(hào)為1..N的牛棚.牛路i連接牛棚a_i (1 <= a_i <= N)和b_i (1 <= b_i <= N)并且需要時(shí)間t_i (1 <=t_i <= 1,000)通過. 沒有兩條牛路連接同樣的牛棚,所有牛路滿足a_i!=b_i.在所有數(shù)據(jù)中,牛_i使用的牛棚_1到牛 棚_i的最短路經(jīng)是唯一的.以下是一個(gè)牛棚,牛路和時(shí)間的例子:1--[2]--2-------+| | |[2] [1] [3]| | |+-------3--[4]--4行程 最佳路經(jīng) 最佳時(shí)間 最后牛路 p_1 到 p_2 1->2 2 1->2 p_1 到 p_3 1->3 2 1->3 p_1 到 p_4 1->2->4 5 2->4當(dāng)gremlins進(jìn)入農(nóng)場(chǎng)后:行程 最佳路經(jīng) 最佳時(shí)間 避免 p_1 到 p_2 1->3->2 3 1->2 p_1 到 p_3 1->2->3 3 1->3 p_1 到 p_4 1->3->4 6 2->420%的數(shù)據(jù)滿足N<=200.50%的數(shù)據(jù)滿足N<=3000.時(shí)間限制: 3秒內(nèi)存限制: 64 MBPROBLEM NAME: travel輸入格式:* 第一行: 兩個(gè)空格分開的數(shù), N和M* 第2..M+1行: 三個(gè)空格分開的數(shù)a_i, b_i,和t_i樣例輸入 (travel.in):4 5 1 2 2 1 3 2 3 4 4 3 2 1 2 4 3輸入解釋:跟題中例子相同輸出格式:* 第1..N-1行: 第i行包含一個(gè)數(shù):從牛棚_1到牛棚_i+1并且避免從牛棚1到牛棚i+1最 短路經(jīng)上最后一條牛路的最少的時(shí)間.如果這樣的路經(jīng)不存在,輸出-1.樣例輸出 (travel.out):3 3 6


題解：
好題珍藏
由于最短路徑唯一，那么可以把到1的最短路徑連起來，形成最短路樹（本蒟蒻這不懂套路）
然后我們根據(jù)題意知道，1-x的路徑中，不能走的為x的父親邊，那么我們就設(shè)法繞開這條邊
于是想到合法情況：從1開始先繞到非x的子樹上的一個(gè)節(jié)點(diǎn)u，再通過該節(jié)點(diǎn)繞道x子樹上一個(gè)節(jié)點(diǎn)p再從p到x
答案即為f[u]+dis(u,p)+f[p]-f[x]
那么想到用堆維護(hù)f[u]+dis(u,p)+f[p] 然后用左偏樹合并，并用并查集判斷是否在x的子樹內(nèi)即可
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <cmath> 6 #include <queue> 7 #include <vector> 8 using namespace std; 9 const int N=100005,M=200005,inf=2e9; 10 int head[N],num=0; 11 struct Lin{ 12 int next,to,dis; 13 }a[M<<1],e[M<<1]; 14 void init(int x,int y,int dis){ 15 a[++num].next=head[x];a[num].to=y;a[num].dis=dis;head[x]=num; 16 } 17 int n,m; 18 int gi(){ 19 int str=0;char ch=getchar(); 20 while(ch>'9' || ch<'0')ch=getchar(); 21 while(ch>='0' && ch<='9')str=(str<<1)+(str<<3)+ch-48,ch=getchar(); 22 return str; 23 } 24 struct pr{ 25 int id,dis; 26 bool operator <(const pr &pp)const{ 27 return dis>pp.dis; 28 } 29 }; 30 priority_queue<pr>q; 31 bool vis[N];int f[N],pre[N]; 32 void dj(){ 33 int cnt=0,x,u,dis; 34 for(int i=1;i<=n;i++)f[i]=inf; 35 q.push((pr){1,0});f[1]=0; 36 while(!q.empty()){ 37 x=q.top().id;dis=q.top().dis;q.pop(); 38 if(vis[x] || f[x]!=dis)continue; 39 cnt++;vis[x]=true;if(cnt==n)break; 40 for(int i=head[x];i;i=a[i].next){ 41 u=a[i].to; 42 if(f[x]+a[i].dis<f[u])f[u]=f[x]+a[i].dis,pre[u]=x; 43 q.push((pr){u,f[u]}); 44 } 45 } 46 } 47 int fa[N],ans[N]; 48 int find(int x){ 49 return fa[x]==x?x:fa[x]=find(fa[x]); 50 } 51 struct node{ 52 int val,dis,id; 53 node *l,*r; 54 int ldis(){return l?l->dis:0;} 55 int rdis(){return r?r->dis:0;} 56 }T[N*10]; 57 node *root[N],*pos=T; 58 node *merge(node *p,node *q){ 59 if(!p || !q)return p?p:q; 60 if(p->val>q->val)swap(p,q); 61 p->r=merge(p->r,q); 62 if(p->ldis()<p->rdis())swap(p->l,p->r); 63 p->dis=p->rdis()+1; 64 return p; 65 } 66 void delet(int x){ 67 root[x]=merge(root[x]->r,root[x]->l); 68 } 69 void dfs(int x,int last){ 70 int u; 71 fa[x]=x; 72 for(int i=head[x];i;i=a[i].next){ 73 u=a[i].to;if(u==last)continue; 74 if(f[x]+a[i].dis==f[u]){ 75 dfs(u,x); 76 fa[find(u)]=find(x); 77 root[x]=merge(root[x],root[u]); 78 } 79 } 80 node *tmp; 81 for(int i=head[x];i;i=a[i].next){ 82 u=a[i].to; 83 if(u==last || find(u)==find(x))continue; 84 tmp=pos++;tmp->l=NULL;tmp->r=NULL;tmp->val=f[u]+a[i].dis+f[x];tmp->id=u; 85 root[x]=merge(root[x],tmp); 86 } 87 while(root[x] && find(root[x]->id)==find(x))delet(x); 88 if(root[x])ans[x]=root[x]->val-f[x]; 89 else ans[x]=-1; 90 } 91 void work() 92 { 93 int x,y,z; 94 n=gi();m=gi(); 95 for(int i=1;i<=m;i++){ 96 x=gi();y=gi();z=gi(); 97 init(x,y,z);init(y,x,z); 98 } 99 dj();dfs(1,1); 100 for(int i=2;i<=n;i++)printf("%d\n",ans[i]); 101 } 102 int main() 103 { 104 freopen("travel.in","r",stdin); 105 freopen("travel.out","w",stdout); 106 work(); 107 }

?

?

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

總結(jié)

以上是生活随笔為你收集整理的[USACO Jan09] 安全路径的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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