1110. 最长路

单点时限: 2.0 sec

内存限制: 256 MB

设 G 为有 n 个顶点的有向无环图,G 中各顶点的编号为 1 到 n,且当 为 G 中的一条边时有 i < j。设 w (i,j)为边 的长度,请设计动态规划算法,计算图 G 中 间的最长路径。输入一个 n,表示这个图中有 n 个顶点,后一个 m,表示有 m 对路径 ,有向,后一个数 p, 表示有 p 次询问,在接下来的 p 行中每行输入 2 个数 a,b,算出此图中从 a 到 b 的最长路径。

输入格式

输入一个数 n(1<=n<=200),表示有 n 个点,接下来一个数 m,表示有 m 条路,接下来 m 行中每行输入 2 个数 a ,b,v 表示从 a 点到 b 点有条路,路的长度为 v。

接下来输入一个数 p,表示有 p 次询问,在接下来的 p 行中每行输入 2 个数 a,b,算出此图中从 a 到 b 的最长路径。

输出格式

对每个询问 p,(a,b),输出从 a 到 b 之间的最长路 . 如果 a,b 之间没连通,输出-1。

样例

Input
4 4
1 2 2
2 3 3
1 3 4
3 4 2
3
1 2
1 3
1 4
Output
2
5
7

209 人解决,263 人已尝试。

285 份提交通过,共有 1001 份提交。

2.8 EMB 奖励。

创建: 13 年,3 月前.

修改: 2 年,10 月前.

最后提交: 2 周,2 天前.

来源: N/A

题目标签