The original problem is in Korean and I can’t find any translated version, so I just rephrase the problem here.
There is a city represented by a connected graph with N nodes (N <= 100000) and bidirectional M weighted edges connecting these nodes. Each node is adjacent to at most five edges, and all weights are positive. Among the nodes, exactly three of them are residential areas. Let’s denote them as A, B, and C. You want to build a store at one of the nodes such that the distances to the residential districts are small. Among all the candidate locations, some of them are strictly worse then the others. For example, let p and q be candidate locations, and the distances to the residential areas from p be a, b, c, and the distances from q be x, y, z. If a > x, b > y, and c > z, p is strictly worse than q and we don’t want to build a store there. Given Q queries about the candidate locations (Q <= N), determine whether they are strictly worse than some other locations or not.
Quite an easy graph problem. Basically, each location can be represented as a triplet (x, y, z), where the numbers denote the distance to the residential areas. Then, we want to find all “minimal” (not “minimum”) elements. The first step is to compute the minimum distances from A, B, and C, and this can be done by running Dijkstra’s algorithm three times. This step takes O(N log N) time since the degree of each node is at most 5, which is constant. After generating all these triplets, we sort them by the first coordinate, leaving only (y, z) pairs. Now, (y2, z2) is worse than (y1, z1) if (y1, z1) appears earlier in the list and has y1 < y2 and z1 < z2. The second step is to find all pairs that are worse than something else. I implemented this by using a binary indexed tree. For the current (y2, z2) pair, find the minimum value of z1 whose y1 value is smaller than y2. If z1 < z2, we check (y2, z2) as bad. Otherwise, we put z2 into the tree at location y2, so that we can look up this value later on. The time complexity is therefore O(N log N). Here is my not-very-clean source code. But it works. Whatever.
#include<cstdio>
#include<map>
#include<queue>
#include<set>
#include<algorithm>
#define mp make_pair
using namespace std;
FILE *ifp=fopen("input.txt", "r");
FILE *ofp=fopen("output.txt", "w");
struct edge{int e, len;};
struct coord
{
int x, y, z, ind;
const bool operator < (const coord& o) const
{
if(x!=o.x) return x<o.x;
if(y!=o.y) return y<o.y;
if(z!=o.z) return z<o.z;
return ind<o.ind;
}
};
const int inf=2000000000;
int n;
int deg[131072];
edge a[131072][8];
int dis[3][131072];
bool chk[131072];
coord b[131072];
bool bad[131072];
int c[262144], sp;
void dijkstra(int s, int *d)
{
int i;
for(i=1;i<=n;i++) d[i]=inf;
d[s]=0;
memset(chk, false, sizeof(chk));
priority_queue<pair<int, int> > q;
q.push(mp(0, s));
while(!q.empty())
{
pair<int, int> cur=q.top(); q.pop();
int x=cur.second, dis=-cur.first;
if(dis>d[x] || chk[x]) continue;
chk[x]=true;
for(i=1;i<=deg[x];i++)
{
if(d[a[x][i].e]<=dis+a[x][i].len) continue;
d[a[x][i].e]=dis+a[x][i].len;
q.push(mp(-d[a[x][i].e], a[x][i].e));
}
}
map<int, int> newdis;
set<int> diss;
set<int>::iterator it;
for(i=1;i<=n;i++) diss.insert(d[i]);
for(i=0, it=diss.begin();it!=diss.end();i++, ++it)
newdis[*it]=i;
for(i=1;i<=n;i++) d[i]=newdis[d[i]];
}
int get_minimum(int s, int e)
{
int ret=inf;
s+=sp; e+=sp;
while(s<=e)
{
if(s==e)
{
ret=min(ret, c[s]);
break;
}
if(s&1){ret=min(ret, c[s]); s=(s+1)>>1;}
else s>>=1;
if(e&1) e>>=1;
else{ret=min(ret, c[e]); e=(e-1)>>1;}
}
return ret;
}
void insert_bit(int x, int val)
{
x+=sp;
while(x && c[x]>val){c[x]=val; x>>=1;}
}
int main()
{
int i, j;
int m;
int s1, s2, s3;
fscanf(ifp, "%d", &n);
fscanf(ifp, "%d%d%d", &s1, &s2, &s3);
fscanf(ifp, "%d", &m);
while(m--)
{
int s, e, len;
fscanf(ifp, "%d%d%d", &s, &e, &len);
a[s][++deg[s]].e=e; a[s][deg[s]].len=len;
a[e][++deg[e]].e=s; a[e][deg[e]].len=len;
}
dijkstra(s1, &dis[0][0]);
dijkstra(s2, &dis[1][0]);
dijkstra(s3, &dis[2][0]);
for(i=1;i<=n;i++)
{
b[i].x=dis[0][i];
b[i].y=dis[1][i];
b[i].z=dis[2][i];
b[i].ind=i;
}
sort(&b[1], &b[n+1]);
for(sp=1;sp<n;sp<<=1);
for(i=1;i<(sp<<1);i++) c[i]=inf;
for(i=1;i<=n;i=j)
{
for(j=i;b[j].x==b[i].x;j++)
{
if(get_minimum(0, b[j].y-1)<b[j].z) bad[b[j].ind]=true;
}
for(j=i;b[j].x==b[i].x;j++)
insert_bit(b[j].y, b[j].z);
}
fscanf(ifp, "%d", &m);
while(m--)
{
fscanf(ifp, "%d", &i);
fprintf(ofp, "%s\n", bad[i]?"NO":"YES");
}
return 0;
}
