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。。。
然后将询问排序。。用并查集维护联通点集、、
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 | #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)
