4144: [AMPPZ2014]Petrol
Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 266 Solved: 99
[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
对于一次行走显然的如果开始时油是满的。。。那么可以走最远。。所以我们可以对每一个点求出距它最近的加油站的距离dis[x]。。然后重置每一条边的边权为dis[x]+dis[y]+v。。。
然后将询问排序。。用并查集维护联通点集、、
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 400010;
struct data{int x,y,s,next;} e[N<<1];
struct node{int x,y,s;} w[N<<1];
struct Data{int x,y,b,id,ans;} q[N];
int T[12000010],f[N],dis[N],vis[N],head[N],c[N],n,m,s,h,t,cnt,sum,x,y,Q,S;
bool cmp(node a,node b){return a.s<b.s;}
bool cmpb(Data a,Data b){return a.b<b.b;}
bool cmpid(Data a,Data b){return a.id<b.id;}
int read(){
int x = 0,f = 1,c = getchar();
while (c<'0' || c>'9') {if (c=='-') f = -1;c = getchar();}
while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
return x*f;
}
void Insert(int x,int y,int s){
e[++cnt].x = x;e[cnt].y = y;e[cnt].s = s;
e[cnt].next = head[x];head[x] = cnt;
}
void Spfa(){
for (int i=1;i<=n;i++) dis[i] = 2e9;
h = t = 0;
for (int i=1;i<=S;i++) dis[c[i]] = 0,T[++t] = c[i],vis[c[i]] = 1;
while (h<t){
int now = T[++h];vis[now] = 0;
for (int i=head[now];i;i=e[i].next)
if (dis[e[i].y]>dis[now]+e[i].s){
dis[e[i].y] = dis[now]+e[i].s;
if (!vis[e[i].y]){vis[e[i].y] = 1;T[++t] = e[i].y;}
}
}
}
int get(int x){return f[x]==x?x:f[x] = get(f[x]);}
void Line(int x,int y){
if (!x || !y) return;
int fx = get(x),fy = get(y);
if (fx==fy) return;
else f[fx] = fy;
}
int main(){
n = read();S = read();m = read();
for (int i=1;i<=S;i++) c[i] = read();
for (int i=1;i<=m;i++){
x = read();y = read();s = read();
Insert(x,y,s);Insert(y,x,s);
}
Spfa();
for (x=1;x<=n;x++)
for (int i=head[x];i;i=e[i].next)
if (e[i].y>x) w[++sum] = (node){x,e[i].y,dis[x]+dis[e[i].y]+e[i].s};
sort(w+1,w+1+sum,cmp);
Q = read();
for (int i=1;i<=Q;i++) q[i].x = read(),q[i].y = read(),q[i].b = read(),q[i].id = i;
sort(q+1,q+1+Q,cmpb);
for (int i=1;i<=n;i++) f[i] = i;
int k = 1;
for (int i=1;i<=Q;i++){
while (w[k].s<=q[i].b && k<=sum) Line(w[k].x,w[k].y),k++;
int fx = get(q[i].x),fy = get(q[i].y);
if (fx==fy) q[i].ans = 1;
else q[i].ans = 0;
}
sort(q+1,q+1+Q,cmpid);
for (int i=1;i<=Q;i++)
if (q[i].ans) printf("TAK\n");
else printf("NIE\n");
}
评论 (0)
