小红的老公小白是个考古学家，有一天小白发现了只白白圆圆小小的木乃伊，它是个爱哭鬼却很努力。小白想把这么可爱的小木乃伊送给老婆，于是便找上了快递姐姐，这下可让快递姐姐犯愁了，因为去往小红家的路实在太难走了（甚至有可能没有路能走到小红家），快递姐姐找上聪明的你，想请你帮忙找出最快到达小红家的路，你行吗？
寻找最短路用到搜索spfa太麻烦了，所以把题目简化一下
只需要找到两个城市是否有直接相连的道路
问题 B: 帮小白送快递魔改版
时间限制: 1 Sec 内存限制: 128 MB提交: 0 解决: 44
[提交][状态][讨论版][命题人:]
题目描述
输入描述
第一行输入两个整数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之间是否有直接相连的道路
接下来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“代表没有
”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
-
Anything about this OnlineJudge, Please Contact Administrator. Click add QQ
OJ system based on HUSTOJ Project , UI based on Twitter Bootstrap
Copyright 2016 ACM算法攻关部
关于网站改版