旅行者

题目描述:

 

输出格式:

 输出文件为tourist.out。

输出共 行，每行包含一个整数表示从一个路口到另一个路口最少需要花的时间。

样例输入:

样例1：
2 2
2
3
6 4
2
1 1 2 2
1 2 2 1

样例2：
2 3
558 163
102 2000
461 1732 561
2
2 1 2 3
1 2 2 2

样例输出:

样例1：
6
7


样例2：
1743
1121

提示:

 

【样例输入输出3】

见选手目录下的tourist/tourist.in与tourist/tourist.ans。(第一题中下载)

【数据规模和约定】

对于所有的测试数据，保证相邻路口之间的时间不超过 ，即 1<=r_ij、c_ij<=10⁴。

各测试点满足以下约定：

时间限制: 2000ms
空间限制: 512MB

---

来源: 浙江省选2016day1t2