Responsive image

问题 2843 --帮小白送快递魔改版

2843: 帮小白送快递魔改版

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 44
[提交][状态][讨论版][命题人:]

题目描述

小红的老公小白是个考古学家，有一天小白发现了只白白圆圆小小的木乃伊，它是个爱哭鬼却很努力。小白想把这么可爱的小木乃伊送给老婆，于是便找上了快递姐姐，这下可让快递姐姐犯愁了，因为去往小红家的路实在太难走了（甚至有可能没有路能走到小红家），快递姐姐找上聪明的你，想请你帮忙找出最快到达小红家的路，你行吗？


寻找最短路用到搜索spfa太麻烦了，所以把题目简化一下
只需要找到两个城市是否有直接相连的道路

输入描述

第一行输入两个整数n和m（2<=n<=m<=200000），分别表示有n座城市和m条路，城市编号为1~n（快递姐姐所在城市为1，小红所在城市为n）。
接下来m行，每行输入3个整数u,v,w（u,v<=n，0<w<=100000），分别表示城市u和城市v之间有一条长为w的路。
第m+2行输入一个整数l（2<=L<=200000），代表l次询问
接下来L行，每行输入2个整数uL，vL（uL,vL<=n）询问城市uL和vl之间是否有直接相连的道路

输出描述

输出L行每行一个数字”0“或”1“代表每对ul和vl之间是否有直接相连的道路
”1“代表有
”0“代表没有

样例输入

4 4
1 2 1
2 3 2
3 4 3
2 3 1
3
1 3
1 2
2 3

样例输出

0
1
1

提示

tle="" align="left" /> 

 样例如图所示

1 3之间没有直接相连的道路输出0

1 2之间有直接相连的道路输出1

2 3之间有直接相连的道路输出1

来源

21软五单勋蓬 

[提交][状态]
ACM算法攻关部