Gremlins最近在农场上泛滥,它们经常会阻止牛们从农庄(牛棚_1)走到别的牛棚(牛_i的目的
地是牛棚_i).每一个gremlin只认识牛_i并且知道牛_i一般走到牛棚_i的最短路经.所以它
们在牛_i到牛棚_i之前的最后一条牛路上等牛_i. 当然,牛不愿意遇到Gremlins,所以准备找
一条稍微不同的路经从牛棚_1走到牛棚_i.所以,请你为每一头牛_i找出避免gremlin_i的最
短路经的长度.
和以往一样, 农场上的M (2 <= M <= 200,000)条双向牛路编号为1..M并且能让所有牛到
达它们的目的地, N(3 <= N <= 100,000)个编号为1..N的牛棚.牛路i连接牛棚a_i
(1 <= a_i <= N)和b_i (1 <= b_i <= N)并且需要时间t_i (1 <=t_i <= 1,000)通过.
没有两条牛路连接同样的牛棚,所有牛路满足a_i!=b_i.在所有数据中,牛_i使用的牛棚_1到牛
棚_i的最短路经是唯一的.
以下是一个牛棚,牛路和时间的例子:
1--[2]--2-------+
| | |
[2] [1] [3]
| | |
+-------3--[4]--4
行程 最佳路经 最佳时间 最后牛路
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
当gremlins进入农场后:
行程 最佳路经 最佳时间 避免
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->4
20%的数据满足N<=200.
50%的数据满足N<=3000.
时间限制: 3秒
内存限制: 64 MB
PROBLEM NAME: travel
输入格式:
* 第一行: 两个空格分开的数, N和M
* 第2..M+1行: 三个空格分开的数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行包含一个数:从牛棚_1到牛棚_i+1并且避免从牛棚1到牛棚i+1最
短路经上最后一条牛路的最少的时间.如果这样的路经不存在,输出-1.
样例输出 (travel.out):
3
3
6
题解：
好题珍藏
由于最短路径唯一，那么可以把到1的最短路径连起来，形成最短路树（本蒟蒻这不懂套路）
然后我们根据题意知道，1-x的路径中，不能走的为x的父亲边，那么我们就设法绕开这条边
于是想到合法情况：从1开始先绕到非x的子树上的一个节点u，再通过该节点绕道x子树上一个节点p再从p到x
答案即为f[u]+dis(u,p)+f[p]-f[x]
那么想到用堆维护f[u]+dis(u,p)+f[p] 然后用左偏树合并，并用并查集判断是否在x的子树内即可
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
",ans[i]);
101 }
102 int main()
103 {
104 freopen("travel.in","r",stdin);
105 freopen("travel.out","w",stdout);
106 work();
107 }