1576: [Usaco2009 Jan]安全路经Travel
Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 665 Solved: 227
[Submit][Status]
Description
Input
* 第一行: 两个空格分开的数, N和M
* 第2..M+1行: 三个空格分开的数a_i, b_i,和t_i
Output
* 第1..N-1行: 第i行包含一个数:从牛棚_1到牛棚_i+1并且避免从牛棚1到牛棚i+1最短路经上最后一条牛路的最少的时间.如果这样的路经不存在,输出-1.
Sample Input
4 5
1 2 2
1 3 2
3 4 4
3 2 1
2 4 3
1 2 2
1 3 2
3 4 4
3 2 1
2 4 3
输入解释:
跟题中例子相同
Sample Output
3
3
6
3
6
输出解释:
跟题中例子相同
HINT
Source
这道题本来的思路是对于每个子树维护一个单调队列，但是看着写链剖都能T的那么惨，还是老老实实写链剖吧。
这道题给我最大的启示是：最短路用spfa是非常作死的。。。。。不过以前我都默认spfa最坏为nlogn的。
至少我一整个下午都没有想到usaco的题居然还要卡spfa。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 110000
#define MAXQ MAXN*20
#define MAXE (MAXN*4 +MAXN*2)
#define MAXV MAXN
#define INF 0x3f3f3f3f
#define lch (now<<1)
#define rch (now<<1^1)
int n,m;
inline int nextInt()
{
register int x=;
register char ch;
while (ch=getchar(),ch<'' || ch>'');
while (x=x*+ch-'',ch=getchar(),ch<='' && ch>='');
return x;
}
struct sgt_node
{
int l,r,val,lazy;
}sgt[MAXN*];
inline void down(int now)
{
sgt[lch].val=min(sgt[lch].val,sgt[now].val);
sgt[rch].val=min(sgt[rch].val,sgt[now].val);
}
void Build_sgt(int now,int l,int r)
{
sgt[now].l=l;sgt[now].r=r;
if (sgt[now].l==sgt[now].r)
{
sgt[now].val=INF;
return ;
}
Build_sgt(lch,l,(l+r)>>);
Build_sgt(rch,((l+r)>>)+,r);
sgt[now].val=max(sgt[lch].val,sgt[rch].val);
}
void Modify_sgt(int now,int l,int r,int v)
{
if (sgt[now].l==l && sgt[now].r==r)
{
sgt[now].val=min(sgt[now].val,v);
return ;
}
down(now);
int mid=(sgt[now].l+sgt[now].r)>>;
if (r<=mid)
Modify_sgt(lch,l,r,v);
else if (mid<l)
Modify_sgt(rch,l,r,v);
else
Modify_sgt(lch,l,mid,v),Modify_sgt(rch,mid+,r,v);
}
int Query_sgt(int now,int pos)
{
if (sgt[now].l==sgt[now].r)return sgt[now].val;
if (pos<=((sgt[now].l+sgt[now].r)>>))
return min(sgt[now].val,Query_sgt(lch,pos));
else
return min(sgt[now].val,Query_sgt(rch,pos));
}
struct Edge
{
int np,val;
Edge *next;
Edge *neg;
}E[MAXE],*V[MAXV],*V2[MAXV];
int tope=-;
inline void addedge(int x,int y,int z)
{
E[++tope].np=y;
E[tope].val=z;
E[tope].next=V[x];
V[x]=&E[tope];
}
inline void addedge2(int x,int y,int z)
{
E[++tope].np=y;
E[tope].val=z;
E[tope].next=V2[x];
V2[x]=&E[tope];
}
int q[MAXQ];
bool vis[MAXN];
int pnt[MAXN];
int dis[MAXN];
Edge *pne[MAXN];
/*
void spfa(register int now)
{
register int head=-1,tail=0;
memset(dis,INF,sizeof(dis));
q[0]=now;
dis[now]=0;
register Edge *ne;
while (head!=tail)
{
head++;
if (head==MAXQ)head=0;
now=q[head];
vis[now]=false;
for (ne=V[now];ne;ne=ne->next)
{
if (dis[ne->np]>dis[now]+ne->val)
{
dis[ne->np]=dis[now]+ne->val;
pne[ne->np]=ne->neg;
pnt[ne->np]=now;
if (!vis[ne->np])
{
tail++;
if (tail==MAXQ)tail=0;
q[tail]=ne->np;
vis[ne->np]=true;
}
}
}
}
}*/
pair<int,int> h[MAXQ];
void dijkstrea(int now)
{
memset(dis,INF,sizeof(dis));
dis[now]=;
int toph=;
Edge *ne;
h[toph]=make_pair(-,now);
push_heap(h,h+(++toph));
while (~toph)
{
if (h[].first!=-dis[h[].second])
{
pop_heap(h,h+(toph--));
continue;
}
for (ne=V[h[].second];ne;ne=ne->next)
{
if (dis[ne->np]>dis[h[].second] + ne->val)
{
dis[ne->np]=dis[h[].second]+ne->val;
pnt[ne->np]=h[].second;
pne[ne->np]=ne->neg;
h[toph]=make_pair(-dis[ne->np],ne->np);
push_heap(h,h+(++toph));
}
}
pop_heap(h,h+(toph--));
}
}
int son[MAXN];
int top[MAXN];
int depth[MAXN];
int pos[MAXN],dfstime=;
int dfs1(int now)
{
register Edge *ne;
int mxsiz=;
int siz=,t;
for (ne=V2[now];ne;ne=ne->next)
{
depth[ne->np]=depth[now]+;
siz+=t=dfs1(ne->np);
if (t>mxsiz)
{
mxsiz=t;
son[now]=ne->np;
}
}
return siz;
}
void dfs2(int now,int tp)
{
register Edge *ne;
pos[now]=++dfstime;
top[now]=tp;
if (~son[now])
dfs2(son[now],tp);
for (ne=V2[now];ne;ne=ne->next)
{
if (ne->np==son[now])continue;
dfs2(ne->np,ne->np);
}
}
int lca(register int x,register int y)
{
while (x!=y)
{
if (top[x]==top[y])
{
if (depth[x]<depth[y])return x;
else return y;
}
if (depth[top[x]]<depth[top[y]])swap(x,y);
x=pnt[top[x]];
}
return x;
}
void work()
{
register Edge *ne;
register int now,i,d,t;
for (i=;i<=n;i++)
{
for(ne=V[i];ne;ne=ne->next)
{
now=i;
if (ne==pne[now])continue;
d=dis[ne->np]+ne->val +dis[now];
t=lca(ne->np,now);
if (t==now)continue;
while (true)
{
if (depth[top[now]]==depth[top[t]])
{
if (pos[t]+<=pos[now])
Modify_sgt(,pos[t]+,pos[now],d);
break;
}
Modify_sgt(,pos[top[now]],pos[now],d);
now=pnt[top[now]];
}
}
}
int ans;
for (i=;i<=n;i++)
{
ans=-dis[i]+Query_sgt(,pos[i]);
if (ans+dis[i]==INF)
printf("-1\n");
else
printf("%d\n",ans);
}
}
int main()
{
freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
int i,j,k,x,y,z;
n=nextInt();m=nextInt();
for (i=;i<m;i++)
{
x=nextInt(),y=nextInt(),z=nextInt();
addedge(x,y,z);
addedge(y,x,z);
V[x]->neg=V[y];
V[y]->neg=V[x];
}
dijkstrea();
memset(son,-,sizeof(son));
for (i=;i<=n;i++)
addedge2(pnt[i],i,INF);
dfs1();
dfs2(,);
Build_sgt(,,dfstime);
work();
}