BZOJ 4144（AMPPZ 2014）Petrol（最短路+最小生成树）

发表于 |
字数统计: 968字 | 阅读时长 ≈ 5min

【AMPPZ2014】加油

问题描述

给定一个n个点、m条边的带权无向图，其中有s个点是加油站。

每辆车都有一个油量上限b，即每次行走距离不能超过b，但在加油站可以补满。

q次询问，每次给出x,y,b，表示出发点是x，终点是y，油量上限为b，且保证x点和y点都是加油站，请回答能否从x走到y。

输入格式

第一行包含三个正整数n,s,m(2<=s<=n<=200000,1<=m<=200000)，表示点数、加油站数和边数。

第二行包含s个互不相同的正整数c[1],c[2],…c[s] (1<=c[i]<=n)，表示每个加油站。

接下来m行，每行三个正整数u[i],v[i],di，表示u[i]和v[i]之间有一条长度为d[i]的双向边。

接下来一行包含一个正整数q(1<=q<=200000)，表示询问数。

接下来q行，每行包含三个正整数x[i],y[i],b[i] (1<=x[i],y[i]<=n,x[i]!=y[i],1<=b[i]<=2*10^9)，表示一个询问。

输出格式

输出q行。第i行输出第i个询问的答案，如果可行，则输出TAK，否则输出NIE。

样例输入

6 4 5

1 5 2 6

1 3 1

2 3 2

3 4 3

4 5 5

6 4 5

4

1 2 4

2 6 9

1 5 9

6 5 8

样例输出

TAK

TAK

TAK

NIE

先跑一个多源最短路，求出到每个点最近的加油站是哪里，然后枚举每条边，如果边的两端最近的加油站不同，那么连接这两个加油站，边权为$dis[x]+dis[y]+len$，这样建好图之后离线处理询问，排序之后跑生成树就行了。

正确性的话我们考虑任意两个加油站的连接的路径，路径上一定存在一个分界点，也就是我们枚举的边。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#define ll long long
#define N 400005
using namespace std;
struct node{ll x,y,d,id;}E[N],K[N];
bool operator<(node a,node b){return a.d<b.d;}
ll n,s,m,q,fa[N],c[N],dis[N],pre[N],cnt,F[N],Ans[N];
ll TOT,LA[N],NE[N],ST[N],EN[N],LE[N];
bool mark[N];
queue<ll>Q;
ll GF(ll x){return x==F[x]?x:F[x]=GF(F[x]);}
void Merge(ll x,ll y)
{
	ll fx=GF(x),fy=GF(y);
	if(fx==fy)return;
	F[fx]=fy;
}
void ADD(ll x,ll y,ll z)
{
	TOT++;
	ST[TOT]=x;
	EN[TOT]=y;
	LE[TOT]=z;
	NE[TOT]=LA[x];
	LA[x]=TOT;
}
void SPFA()
{
	while(Q.size())
	{
		ll x=Q.front();
		Q.pop();
		mark[x]=0;
		for(ll i=LA[x];i;i=NE[i])
		{
			ll y=EN[i];
			if(dis[y]>dis[x]+LE[i])
			{
				dis[y]=dis[x]+LE[i];
				pre[y]=pre[x];
				if(!mark[y])mark[y]=1,Q.push(y);
			}
		}
	}
}
int main()
{
	ll i,j,k,x,y,z;
	scanf("%lld%lld%lld",&n,&s,&m);
	fill(dis,dis+n+1,1e18);
	for(i=1;i<=n;i++)F[i]=i;
	for(i=1;i<=s;i++)
	{
		scanf("%lld",&c[i]);pre[c[i]]=c[i];
		dis[c[i]]=0;mark[c[i]]=1;Q.push(c[i]);
	}
	for(i=1;i<=m;i++)
	{
		scanf("%lld%lld%lld",&x,&y,&z);
		ADD(x,y,z);ADD(y,x,z);
	}
	SPFA();scanf("%lld",&q);
	for(i=1;i<=q;i++)
	{
		scanf("%lld%lld%lld",&x,&y,&z);
		K[i]=(node){x,y,z,i};
	}
	for(i=1;i<=TOT;i+=2)
	{
		x=ST[i];y=EN[i];
		if(pre[x]!=pre[y])E[++cnt]=(node){pre[x],pre[y],dis[x]+dis[y]+LE[i],0};
	}
	sort(K+1,K+q+1);
	sort(E+1,E+cnt+1);
	for(i=j=1;i<=q;i++)
	{
		while(j<=cnt&&E[j].d<=K[i].d)Merge(E[j].x,E[j].y),j++;
		if(GF(K[i].x)==GF(K[i].y))Ans[K[i].id]=1;
	}
	for(i=1;i<=q;i++)Ans[i]==1?puts("TAK"):puts("NIE");
}