PKU 1984 Navigation Nightmare
やるだけ。実装が重い(?)せいかなぜか非公式難易度表では8。
あらゆるテストが迫っているので今日はコレだけ。
int N,M,K; struct edge{int to,dir,cost;}; struct query{int from,to,turn;}; vector<edge> G[40010]; P dist[40010];//fi:East sec:North query Q[40010]; P mer[40010]; bool cmp_q(query a,query b) { return a.turn < b.turn; } struct UnionFind { int par[40010],rank[40010]; void init() { memset(rank,0,sizeof(rank)); for(int i=0;i<40010;i++)par[i]=i; return; } int find(int x) { if(par[x]==x)return x; else return find(par[x]); } void unite(int a,int b) { a=find(a); b=find(b); if(rank[a]<rank[b])par[a]=b; else { par[b]=a; if(rank[a]==rank[b])rank[a]++; } } bool same(int a,int b) { return find(a)==find(b); } }uf; void add_edge(int a,int b,int c,int d)//0:East 1:North { edge p,q; p.to=b;p.dir=d;p.cost=c; q.to=a;q.dir=d;q.cost=-c; G[a].pb(p); G[b].pb(q); } void dfs(int v,int p) { for(int i=0;i<G[v].size();i++) { edge e=G[v][i]; if(e.to==p)continue; dist[e.to]=dist[v]; if(e.dir)dist[e.to].sec+=e.cost; else dist[e.to].fi+=e.cost; dfs(e.to,v); } return; } int dis(int p,int q) { return abs(dist[p].fi-dist[q].fi)+abs(dist[p].sec-dist[q].sec); } int main() { uf.init(); scanf("%d %d",&N,&M); for(int i=0;i<M;i++) { int f1,f2,L; char dir; scanf("%d %d %d %c",&f1,&f2,&L,&dir); mer[i].fi=f1; mer[i].sec=f2; if(dir=='E')add_edge(f1,f2,L,0); else if(dir=='W')add_edge(f1,f2,-L,0); else if(dir=='N')add_edge(f1,f2,L,1); else add_edge(f1,f2,-L,1); } dfs(1,-1); scanf("%d",&K); for(int i=0;i<K;i++) { scanf("%d %d %d",&Q[i].from,&Q[i].to,&Q[i].turn); Q[i].turn--; } sort(Q,Q+K,cmp_q); int cnt=0; for(int i=0;i<M;i++) { uf.unite(mer[i].fi,mer[i].sec); if(cnt==K)break; while(Q[cnt].turn==i&&cnt<K) { if(uf.same(Q[cnt].from,Q[cnt].to)) { printf("%d\n",dis(Q[cnt].from,Q[cnt].to)); } else printf("-1\n"); cnt++; } } return 0; }