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的子树内即可
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
using namespace std;
const int N=,M=,inf=2e9;
int head[N],num=;
struct Lin{
int next,to,dis;
}a[M<<],e[M<<];
void init(int x,int y,int dis){
a[++num].next=head[x];a[num].to=y;a[num].dis=dis;head[x]=num;
}
int n,m;
int gi(){
int str=;char ch=getchar();
while(ch>'' || ch<'')ch=getchar();
while(ch>='' && ch<='')str=(str<<)+(str<<)+ch-,ch=getchar();
return str;
}
struct pr{
int id,dis;
bool operator <(const pr &pp)const{
return dis>pp.dis;
}
};
priority_queue<pr>q;
bool vis[N];int f[N],pre[N];
void dj(){
int cnt=,x,u,dis;
for(int i=;i<=n;i++)f[i]=inf;
q.push((pr){,});f[]=;
while(!q.empty()){
x=q.top().id;dis=q.top().dis;q.pop();
if(vis[x] || f[x]!=dis)continue;
cnt++;vis[x]=true;if(cnt==n)break;
for(int i=head[x];i;i=a[i].next){
u=a[i].to;
if(f[x]+a[i].dis<f[u])f[u]=f[x]+a[i].dis,pre[u]=x;
q.push((pr){u,f[u]});
}
}
}
int fa[N],ans[N];
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
struct node{
int val,dis,id;
node *l,*r;
int ldis(){return l?l->dis:;}
int rdis(){return r?r->dis:;}
}T[N*];
node *root[N],*pos=T;
node *merge(node *p,node *q){
if(!p || !q)return p?p:q;
if(p->val>q->val)swap(p,q);
p->r=merge(p->r,q);
if(p->ldis()<p->rdis())swap(p->l,p->r);
p->dis=p->rdis()+;
return p;
}
void delet(int x){
root[x]=merge(root[x]->r,root[x]->l);
}
void dfs(int x,int last){
int u;
fa[x]=x;
for(int i=head[x];i;i=a[i].next){
u=a[i].to;if(u==last)continue;
if(f[x]+a[i].dis==f[u]){
dfs(u,x);
fa[find(u)]=find(x);
root[x]=merge(root[x],root[u]);
}
}
node *tmp;
for(int i=head[x];i;i=a[i].next){
u=a[i].to;
if(u==last || find(u)==find(x))continue;
tmp=pos++;tmp->l=NULL;tmp->r=NULL;tmp->val=f[u]+a[i].dis+f[x];tmp->id=u;
root[x]=merge(root[x],tmp);
}
while(root[x] && find(root[x]->id)==find(x))delet(x);
if(root[x])ans[x]=root[x]->val-f[x];
else ans[x]=-;
}
void work()
{
int x,y,z;
n=gi();m=gi();
for(int i=;i<=m;i++){
x=gi();y=gi();z=gi();
init(x,y,z);init(y,x,z);
}
dj();dfs(,);
for(int i=;i<=n;i++)printf("%d\n",ans[i]);
}
int main()
{
freopen("travel.in","r",stdin);
freopen("travel.out","w",stdout);
work();
}
