「BZOJ3417」POI2013 Tales of seafaring

2014年10月29日4,30123

Description

Young Bytensson loves to hang out in the port tavern, where he often listens to the sea dogs telling their tales of seafaring. Initially, he believed them all, however incredible they sounded. Over time though, he became suspicious. He has decided to write a program that will verify if there may be any grain of truth in those tall stories. Bytensson reasoned that while he cannot tell if the sailors indeed weathered all those storms, he can at least find out if their travel itineraries make sense. This is a task for a programmer, which Bytensson, unfortunately, is not. Help him out!
There are   ports and   waterways connecting them in the waters frequented by the sailors Bytensson listened to. If there is a waterway between two ports, then sailing from one to the other is possible. Any waterway can be sailed in both directions.
Bytensson got to know K seafaring tales. Each tells of a sailor who began his journey in one port, sailed a number of waterways, and ended up in another port, which may have been the one he initially set sail from. The sailor in question may have sailed through the same waterway many times, each time in any direction.

一个n点m边无向图,边权均为1,有k个询问

每次询问给出(s,t,d),要求回答是否存在一条从s到t的路径,长度为d

路径不必是简单路(可以自交)

Input

In the first line of the standard input, there are three integers, N,M and K (2<=N<=5000,1<=M<=5000,1<=K<=1000000) These denote, respectively: the number of ports in the waters frequented by the sailors who told Bytensson their stories, the number of waterways, and the number of tales.
The M lines that follow specify the waterways. A single waterway’s description consists of a single line that contains two integers, a and b (1<=a,b<=N,a<>b) separated by a single space; these specify the numbers of ports at the two ends of this particular waterway.
The K lines that follow specify the tales that Bytensson has heard. A single tale’s description consists of a single line with three integers, s,t  and d (1<=S,T<=N,1<=d<=1000000000) separated by single spaces. These indicate that the tale’s protagonist set sail from port no. s, ended the journey in port no. t, and sailed exactly d times through various waterways.

Output

Your program should print exactly K lines to the standard output; the i-th of them should contain the word TAK (Polish for yes) if the journey described in the i-th tale (in input order) could have taken place. If it could not, then the line should contain the word NIE(Polish for no).

Sample Input

8 7 4
1 2
2 3
3 4
5 6
6 7
7 8
8 5
2 3 1
1 4 1
5 5 8
1 8 10

Sample Output

TAK
NIE
TAK
NIE

题解

http://wenku.baidu.com/link?url=Xsi-1wIc3hQXZLNQx-KVI9bMOgq5HA3VpgG7NbnktJsGDK6Mx3lLXGXJ9lVO5p6nhlWk_zXExPB7kPd1-ek8kiDTOPfVJFoa2rkN5zsThkC

为了防止爆内存可以把询问排序,x相同的分为一块bfs(x)然后记录答案

 

avatar
23 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
0 Comment authors
Recent comment authors
  Subscribe  
提醒
trackback

relógios famosos

Além disso, olhar para alto teor de fibras e proteínas.

trackback

long sleeve wedding dress ideas

wow its great post..

trackback

giuseppe zanotti mesh booties

hey good job man.

trackback

ray ban aviators lenses

nice site, all posts are very nice.

trackback

louis vuitton vernis alma handbag

Thank you admins.

trackback

ray ban 4147 polarized replacement lenses

thank you

trackback

apple green coach purse

Very good, i like you.And say and say ¡­¡­¡­. It’s greatttttttttttt¡­¡­..

trackback

giuseppe zanotti mary jane

thanks, nice post.

trackback

gothic wedding dresses corset

Good job!

trackback

ray ban wayfarer tortoise fake

this is appreciable.!!!!!!i like it.

trackback

wedding dress patterns for plus size

Thank you!!!!

trackback

giuseppe zanotti yellow shoes rosemere

Nice posts indeed

trackback

coach book bags on sale

Valuable thoughts and advices. I read your topic with great interest.

trackback

louis vuitton man bag price uk

Just what I needed, thanks a lot.

trackback

nike air max 90 grey and yellow

Great post.Thanks a lot.

trackback

herve leger elbise istanbul

wonderful post, thank you.

trackback

giuseppe zanotti shoes run small business

Thanks for such a great post and the review, I am totally impressed!

trackback

ray ban 4068 grau

nice and thanks.

trackback

louis vuitton never full bag on sale

this is appreciable.!!!!!!i like it.

trackback

louis vuitton watches for sale

thank you

trackback

coach bag chelsea tote

a very successful site. Also very revealing article. Thanks to the contributors.

trackback

giuseppe zanotti round toe pumps uk

this is just perfect!

trackback

louis vuitton handbags grey and white

Such a good article, caught my sympathy!