「BZOJ1576」[Usaco2009 Jan] 安全路经Travel

2014年8月7日6,5651

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
输入解释:
跟题中例子相同

Sample Output

3
3
6
输出解释:
跟题中例子相同

题解

首先用dijkstra得出最短路径树

然后

我的做法是树链剖分+线段树

对于一条不在最短路树的有向边（无向可看成两条有向）u-v，长度L，设t=lca(u,v)

那么对于t-v的路径上所有点x，都可通过1-t-u-v-x

路径长度为d[u]+L+d[v]-d[x]

最小化这个长度，也就是最小化d[u]+d[v]+L

所以我们可以用这个值去更新t-v所有点（不包括t）的最短路长度

这一步可以用线段树操作。。。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#define pa pair<int,int>
#define ll long long 
#define inf 1000000000
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int bin[20];
int n,m,cnt,sz,place;
int last[100005],dis[100005],from[100005];
int u[200005],v[200005],w[200005];
int fa[100005][17],belong[100005],deep[100005],pl[100005],size[100005];
bool vis[100005],mark[400005];
struct edge{int to,next,v;}e[400005];
struct seg{int l,r,v,tag;}t[400005];
void insert(int u,int v,int w)
{
	e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;
	e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=w;
}
void dijkstra()
{
	priority_queue<pa,vector<pa>,greater<pa> > q;
	for(int i=1;i<=n;i++)dis[i]=inf;
	dis[1]=0;q.push(make_pair(0,1));
	while(!q.empty())
	{
		int now=q.top().second;q.pop();
		if(vis[now])continue;vis[now]=1;
		for(int i=last[now];i;i=e[i].next)
			if(dis[now]+e[i].v<dis[e[i].to])
			{
				dis[e[i].to]=dis[now]+e[i].v;
				mark[from[e[i].to]]=0;from[e[i].to]=i;mark[i]=1;
				q.push(make_pair(dis[e[i].to],e[i].to));
			}
	}
}
void dfs1(int x)
{
	size[x]=1;
	for(int i=1;i<=16;i++)
		if(deep[x]>=bin[i])
			fa[x][i]=fa[fa[x][i-1]][i-1];
		else break;
	for(int i=last[x];i;i=e[i].next)
	{
		if(!mark[i])continue;
		fa[e[i].to][0]=x;
		deep[e[i].to]=deep[x]+1;
		dfs1(e[i].to);
		size[x]+=size[e[i].to];
	}
}
void dfs2(int x,int chain)
{
	belong[x]=chain;pl[x]=++place;
	int k=0;
	for(int i=last[x];i;i=e[i].next)
		if(mark[i]&&size[e[i].to]>size[k])
			k=e[i].to;
	if(k)dfs2(k,chain);
	for(int i=last[x];i;i=e[i].next)
		if(mark[i]&&e[i].to!=k)
			dfs2(e[i].to,e[i].to);
}
int lca(int x,int y)
{
	if(deep[x]<deep[y])swap(x,y);
	int t=deep[x]-deep[y];
	for(int i=0;i<=16;i++)
		if(t&bin[i])x=fa[x][i];
	for(int i=16;i>=0;i--)
		if(fa[x][i]!=fa[y][i])
			x=fa[x][i],y=fa[y][i];
	if(x==y)return x;
	return fa[x][0];
}
void pushdown(int k)
{
	if(t[k].l==t[k].r||t[k].tag==inf)return;
	int tag=t[k].tag;t[k].tag=inf;
	t[k<<1].tag=min(t[k<<1].tag,tag);
	t[k<<1|1].tag=min(t[k<<1|1].tag,tag);
	t[k<<1].v=min(t[k<<1].v,tag);
	t[k<<1|1].v=min(t[k<<1|1].v,tag);
}
void build(int k,int l,int r)
{
	t[k].l=l,t[k].r=r;t[k].v=t[k].tag=inf;
	if(l==r)return;
	int mid=(l+r)>>1;
	build(k<<1,l,mid);build(k<<1|1,mid+1,r);
}
void modify(int k,int x,int y,int v)
{
    pushdown(k);
    int l=t[k].l,r=t[k].r;
    if(x==l&&y==r)
    {
        t[k].tag=min(t[k].tag,v);
        if(l==r)t[k].v=min(v,t[k].v);
        return;
    }
    int mid=(l+r)>>1;
    if(y<=mid)modify(k<<1,x,y,v);
    else if(x>mid)modify(k<<1|1,x,y,v);
    else {modify(k<<1,x,mid,v);modify(k<<1|1,mid+1,y,v);}
}
int query(int k,int x)
{
	pushdown(k);
	int l=t[k].l,r=t[k].r;
	if(l==r)return t[k].v;
	int mid=(l+r)>>1;
	if(x<=mid)return query(k<<1,x);
	else return query(k<<1|1,x);
}
void solve(int x,int f,int val)
{
	while(belong[x]!=belong[f])
	{
		modify(1,pl[belong[x]],pl[x],val);
		x=fa[belong[x]][0];
	}
	if(x!=f)modify(1,pl[f]+1,pl[x],val);
}
int main()
{
	bin[0]=1;for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1;
	n=read();m=read();
	for(int i=1;i<=m;i++)
	{
		u[i]=read(),v[i]=read(),w[i]=read();
		insert(u[i],v[i],w[i]);
	}
	dijkstra();
	dfs1(1);dfs2(1,1);
	build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		int f=lca(u[i],v[i]);
		if(!mark[2*i-1])solve(v[i],f,dis[u[i]]+dis[v[i]]+w[i]);
		if(!mark[2*i])solve(u[i],f,dis[u[i]]+dis[v[i]]+w[i]);
  	}
    for(int i=2;i<=n;i++)
    {
		int t=query(1,pl[i]);
		if(t!=inf)printf("%d\n",t-dis[i]);
		else puts("-1");
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cstring>

#define pa pair<int,int>

#define ll long long

#define inf 1000000000

using namespace std;

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int bin[20];

int n,m,cnt,sz,place;

int last[100005],dis[100005],from[100005];

int u[200005],v[200005],w[200005];

int fa[100005][17],belong[100005],deep[100005],pl[100005],size[100005];

bool vis[100005],mark[400005];

struct edge{int to,next,v;}e[400005];

struct seg{int l,r,v,tag;}t[400005];

void insert(int u,int v,int w)

{

e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;

e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=w;

}

void dijkstra()

{

priority_queue<pa,vector<pa>,greater<pa> > q;

for(int i=1;i<=n;i++)dis[i]=inf;

dis[1]=0;q.push(make_pair(0,1));

while(!q.empty())

{

int now=q.top().second;q.pop();

if(vis[now])continue;vis[now]=1;

for(int i=last[now];i;i=e[i].next)

if(dis[now]+e[i].v<dis[e[i].to])

{

dis[e[i].to]=dis[now]+e[i].v;

mark[from[e[i].to]]=0;from[e[i].to]=i;mark[i]=1;

q.push(make_pair(dis[e[i].to],e[i].to));

}

void dfs1(int x)

{

size[x]=1;

for(int i=1;i<=16;i++)

if(deep[x]>=bin[i])

fa[x][i]=fa[fa[x][i-1]][i-1];

else break;

for(int i=last[x];i;i=e[i].next)

{

if(!mark[i])continue;

fa[e[i].to][0]=x;

deep[e[i].to]=deep[x]+1;

dfs1(e[i].to);

size[x]+=size[e[i].to];

}

void dfs2(int x,int chain)

{

belong[x]=chain;pl[x]=++place;

int k=0;

for(int i=last[x];i;i=e[i].next)

if(mark[i]&&size[e[i].to]>size[k])

k=e[i].to;

if(k)dfs2(k,chain);

for(int i=last[x];i;i=e[i].next)

if(mark[i]&&e[i].to!=k)

dfs2(e[i].to,e[i].to);

}

int lca(int x,int y)

{

if(deep[x]<deep[y])swap(x,y);

int t=deep[x]-deep[y];

for(int i=0;i<=16;i++)

if(t&bin[i])x=fa[x][i];

for(int i=16;i>=0;i--)

if(fa[x][i]!=fa[y][i])

x=fa[x][i],y=fa[y][i];

if(x==y)return x;

return fa[x][0];

}

void pushdown(int k)

{

if(t[k].l==t[k].r||t[k].tag==inf)return;

int tag=t[k].tag;t[k].tag=inf;

t[k<<1].tag=min(t[k<<1].tag,tag);

t[k<<1|1].tag=min(t[k<<1|1].tag,tag);

t[k<<1].v=min(t[k<<1].v,tag);

t[k<<1|1].v=min(t[k<<1|1].v,tag);

}

void build(int k,int l,int r)

{

t[k].l=l,t[k].r=r;t[k].v=t[k].tag=inf;

if(l==r)return;

int mid=(l+r)>>1;

build(k<<1,l,mid);build(k<<1|1,mid+1,r);

}

void modify(int k,int x,int y,int v)

{

pushdown(k);

int l=t[k].l,r=t[k].r;

if(x==l&&y==r)

{

t[k].tag=min(t[k].tag,v);

if(l==r)t[k].v=min(v,t[k].v);

return;

}

int mid=(l+r)>>1;

if(y<=mid)modify(k<<1,x,y,v);

else if(x>mid)modify(k<<1|1,x,y,v);

else {modify(k<<1,x,mid,v);modify(k<<1|1,mid+1,y,v);}

}

int query(int k,int x)

{

pushdown(k);

int l=t[k].l,r=t[k].r;

if(l==r)return t[k].v;

int mid=(l+r)>>1;

if(x<=mid)return query(k<<1,x);

else return query(k<<1|1,x);

}

void solve(int x,int f,int val)

{

while(belong[x]!=belong[f])

{

modify(1,pl[belong[x]],pl[x],val);

x=fa[belong[x]][0];

}

if(x!=f)modify(1,pl[f]+1,pl[x],val);

}

int main()

{

bin[0]=1;for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1;

n=read();m=read();

for(int i=1;i<=m;i++)

{

u[i]=read(),v[i]=read(),w[i]=read();

insert(u[i],v[i],w[i]);

}

dijkstra();

dfs1(1);dfs2(1,1);

build(1,1,n);

for(int i=1;i<=m;i++)

{

int f=lca(u[i],v[i]);

if(!mark[2*i-1])solve(v[i],f,dis[u[i]]+dis[v[i]]+w[i]);

if(!mark[2*i])solve(u[i],f,dis[u[i]]+dis[v[i]]+w[i]);

}

for(int i=2;i<=n;i++)

{

int t=query(1,pl[i]);

if(t!=inf)printf("%d\n",t-dis[i]);

else puts("-1");

}

return 0;

}

« 「BZOJ2304」[APIO2011] 寻路path 「NOIP模拟赛by wulala」公主的朋友 »

Chenyao

太神了,Orzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz

hzwer.com _ Home | http://hzwer.com

「BZOJ1576」[Usaco2009 Jan] 安全路经Travel

Description

Input

Output

Sample Input

Sample Output

题解

分类目录

热门文章

Myfriends

近期评论