4144: [AMPPZ2014]Petrol
Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 752 Solved: 298
[Submit][Status][Discuss]
Description
给定一个n个点、m条边的带权无向图，其中有s个点是加油站。
每辆车都有一个油量上限b，即每次行走距离不能超过b，但在加油站可以补满。
q次询问，每次给出x,y,b，表示出发点是x，终点是y，油量上限为b，且保证x点和y点都是加油站，请回答能否从x走到y。
Input
第一行包含三个正整数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],d[i](1<=u[i],v[i]<=n,u[i]!=v[i],1<=d[i]<=10000)，表示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)，表示一个询问。
Output
输出q行。第i行输出第i个询问的答案，如果可行，则输出TAK，否则输出NIE。
Sample Input
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
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
Sample Output
TAK
TAK
TAK
NIE
TAK
TAK
NIE
HINT
Source
朴素是先写个多源最短路把加油站的最小生成树所有可能边弄出来，然后后面按部就班地建个最小生成树，然后对树上写个主席树（st倍增）找u到v上最大值，和b比较一下。
那我们在把所有可能边弄出来以后停一下2333，我们连边不要对这条边俩端点连，而是对他们所在块的堆头节点连，这个建出来在查询最大值上是等效的。然后我们启发式地合并堆，这样可以把堆高度控制在logn，就不用再写个主席树啥的那麻烦了。直接两个端点往上一个一个跳，logn的不会有事的。
#include<bits/stdc++.h>
#define clr(x) memset(x,0,sizeof(x))
#define clr_1(x) memset(x,-1,sizeof(x))
#define INF 0x3f3f3f3f
#define LL long long
#define pb push_back
#define mod 1000000007
#define ls(i) (i<<1)
#define rs(i) (i<<1|1)
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef pair<LL,int > pli;
const int N = 2e5+;
bool need[N];
vector<pli> e[N];
struct node
{
int u,v;
LL w;
node(int _u=,int _v=,LL _w=):u(_u),v(_v),w(_w) {}
};
vector<node> ve;
int n,s,m,T;
priority_queue<pli,vector<pli>,greater<pli> > que;
int fuel[N];
int fa[N],rfa[N],rk[N],dep[N];
LL dis[N],val[N];
bool vis[N];
int pre[N];
void dij()
{
while(!que.empty())
{
pli now=que.top();
que.pop();
LL dist=now.fi;
int u=now.se;
if(vis[u]) continue;
vis[u]=;
int sz=e[u].size();
for(int i=;i<sz;i++)
{
pli p=e[u][i];
int w=p.fi;
int v=p.se;
if(!pre[v] || dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
pre[v]=pre[u];
que.push(mp(dis[v],v));
}
else if(pre[u] != pre[v])
ve.pb(node(pre[u],pre[v],dis[u]+dis[v]+w));
}
}
return ;
}
bool cmp(node a,node b)
{
return a.w<b.w;
}
int Find(int u)
{
if(fa[u]!=u)
fa[u]=Find(fa[u]);
return fa[u];
}
void Union()
{
sort(ve.begin(),ve.end(),cmp);
for(int i=;i<=s;i++)
{
fa[fuel[i]]=fuel[i];
rk[fuel[i]]=;
}
int sz=ve.size();
for(int i=;i<sz;i++)
{
node p=ve[i];
int u = p.u, v = p.v;
LL w = p.w;
u = Find(u), v = Find(v);
if(u==v) continue;
if(rk[u]<rk[v]) swap(u,v);
if(rk[u]==rk[v]) rk[u]++;
rfa[v]=u,fa[v]=u,val[v]=w;
}
return ;
}
void dealdep(int u)
{
if(dep[u]>) return ;
if(fa[u]==u)
{
dep[u]=;
return ;
}
dealdep(rfa[u]);
dep[u]=dep[rfa[u]]+;
return ;
}
bool solve(int u,int v,LL b)
{
if(Find(u)!=Find(v)) return ;
if(dep[u]<dep[v]) swap(u,v);
while(dep[u]>dep[v])
{
if(b<val[u]) return ;
u=rfa[u];
}
if(u==v) return ;
while(u!=v)
{
if(b<val[u]) return ;
if(b<val[v]) return ;
u=rfa[u];
v=rfa[v];
}
return ;
}
int main()
{
scanf("%d%d%d",&n,&s,&m);
clr_1(dis);
for(int i=;i<=s;i++)
{
scanf("%d",fuel+i);
que.push(mp(,fuel[i]));
pre[fuel[i]]=fuel[i];
dis[fuel[i]]=;
}
for(int i=;i<=m;i++)
{
int u,v;
LL w;
scanf("%d%d%lld",&u,&v,&w);
e[u].pb(mp(w,v));
e[v].pb(mp(w,u));
}
dij();
Union();
for(int i=;i<=s;i++)
dealdep(fuel[i]);
int u,v;
LL b,maxn;
int q;
scanf("%d",&q);
while(q--)
{
scanf("%d%d%lld",&u,&v,&b);
if(solve(u,v,b))
printf("TAK\n");
else
printf("NIE\n");
}
return ;
}