#P10710. 山遥路远

    ID: 9828 传统题 2000ms 512MiB 尝试: 2 已通过: 2 难度: 9 上传者: 标签>CF2700省选/NOI-Dijkstra辅助点压缩边根号分块增量维护

山遥路远

题目描述

给定一张有 nn 个顶点、mm 条边的有向图。每条边有一个非负长度和一个括号字符,可以是左括号或右括号。

沿有向边行走时,将经过的边的括号按顺序拼接。若结果是合法括号序列,则这次行走合法。允许重复经过顶点和边。空序列也是合法括号序列,因此每个顶点到自身有长度为 00 的合法路径。

有 qq 个询问。每次给定 s,ts,t,求从 ss 到 tt 的最短合法路径的总长度。

输入格式

第一行三个整数 n,m,qn,m,q。接下来 mm 行,每行四个整数 u,v,w,bu,v,w,b,表示从 uu 到 vv 的一条有向边,长度为 ww,b=1b=1 表示左括号,b=2b=2 表示右括号。图中可以有重边和自环。

接下来 qq 行,每行两个整数 s,ts,t。

输出格式

每次询问输出一行一个整数。若不存在合法路径,输出 -1。否则将实际最短长度对 998244353998244353 取模后输出。

样例

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。

数据范围

所有数据满足 1≤n≤4001\le n\le400,1≤m≤5×1041\le m\le5\times10^4,1≤q≤1051\le q\le10^5,0≤w≤1080\le w\le10^8。原赛题所称特殊性质 A 为所有询问均满足 s=1s=1。

原 PDF 题面