#P10710. 山遥路远
山遥路远
题目描述
给定一张有 个顶点、 条边的有向图。每条边有一个非负长度和一个括号字符,可以是左括号或右括号。
沿有向边行走时,将经过的边的括号按顺序拼接。若结果是合法括号序列,则这次行走合法。允许重复经过顶点和边。空序列也是合法括号序列,因此每个顶点到自身有长度为 的合法路径。
有 个询问。每次给定 ,求从 到 的最短合法路径的总长度。
输入格式
第一行三个整数 。接下来 行,每行四个整数 ,表示从 到 的一条有向边,长度为 , 表示左括号, 表示右括号。图中可以有重边和自环。
接下来 行,每行两个整数 。
输出格式
每次询问输出一行一个整数。若不存在合法路径,输出 -1。否则将实际最短长度对 取模后输出。
样例
5 5 5
1 2 100000000 1
2 3 100000000 2
3 1 100000000 1
3 4 100000000 2
4 5 100000000 2
1 1
1 2
1 3
1 4
1 5
0
-1
200000000
600000000
1755647
原题另外在下发文件中提供样例 2。
数据范围
所有数据满足 ,,,。原赛题所称特殊性质 A 为所有询问均满足 。