1259. 飞翔

时间限制 1000 ms   内存限制 128 MB

这些鹰的起始点被设在一个N*M矩阵的左下角map[1,1]的左下角。终点被设定在矩阵的右上角map[N,M]的右上角,有些map[i,j]是可以从中间穿越的。每一个方格的边长都是100米。如图所示:  [img]ProblemImg/P1136.jpg[/img] 没有障碍,也没有死路。这样设计主要是为了高速飞行的鹰们不要发现死路来不及调整而发生意外。潘帕斯雄鹰冒着减RP的危险从比赛承办方戒备森严的基地中偷来了施工的地图。但是问题也随之而来,他必须在比赛开始之前把地图的每一条路都搞清楚,从中找到一条到达终点最近的路。(哈哈,笨鸟不先飞也要拿冠军)但是此鹰是前无古鹰,后无来鹰的吃菜长大的鹰--菜鸟。他自己没有办法得出最短的路径,于是紧急之下找到了学OI的你,希望找到你的帮助。

输入数据

首行为n,m(0< n,m< =100000),第2行为k(0< k< =1000)表示有多少个特殊的边。以下k行为两个数,i,j表示map[i,j]是可以直接穿越的。

输出数据

仅一行,1,1--> n,m的最短路径的长度,四舍五入保留到整数即可

样例输入

复制
3 2
3
1 1
3 2
1 2
 · \n
 \n
 · \n
 · \n
 · \n

样例输出

复制
383
   \n

提交

请先 登录

Source

@潘帕斯雄鹰经典问题改编 本题目由VijosCP  V0.1.1  测试版  生成  请勿删除此行

© 2024 FAQs Contact About