给你一个 \(n\) 个点，\(m\) 条边的有向图，每条有向边有一个长度 \(w\)，且上面有一个字符，这个字符只可能是左括号或者右括号，即 \((\) 或 \()\) 。

我们称一条路径是合法路径，满足其经过的所有字符拼接起来得到的括号串是一个合法括号序列。

接下来有 \(q\) 组询问，每次询问给出节点 \(s,t\) ，问 \(s\) 到 \(t\) 是否存在一条合法路径，如果存在，那么请输出其最短合法路径的长度。由于答案可能很大，你只需要输出答案模 \(998244353\) 的结果。注意这个图可能有重边和自环。

\(1\leq n\leq 400,1\leq m\leq 5\times 10^4,1\leq q\leq 10^5,0\leq w\leq 10^8\)

时限 : 1500ms

空间 : 512mb

看到模 \(998244353\) ，我就害怕了 .

以为本题跟矩阵之类的东西有关，其实不然 .

看到这个最小代价，还可以向最短路上想 .

用 \(f(i,j)\) 表示从节点 \(i\) 到节点 \(j\) 合法串的最小代价.

那么，对于 \(f(i,j)\) 可以扩展到什么 .

1. 把当前合法串和另一个合法串拼在一起

   \([i\to j]+[j\to k]=[i\to k]\) \(f(i,k)=\min(f(i,k),f(i,j)+f(j,k))\)

   \([k\to i]+[i\to j]=[k\to j]\) \(f(k,j)=\min(f(k,j),f(k,i)+f(i,j))\)

2. 在当前串左右两边加上一个括号 \((+[i\to j]+)\)

   \(f(k,l)=f(i,j)+w(i,k)+w(j,l)\)

对于状态 \((i,j)\) 就可以转移到别的状态了 . 最短路的图也就明了了 .

初始状态即是 \(f(i,i)=0\) .

第一种扩展是 \(\mathrm O(n^3)\) 的，第二种是 \(\mathrm O(nm^2)\) 的.

再加上 dijkstra 的 \(\log\)，总的时间复杂度是 \(\mathrm O((n^3+m^2)\log n^2)\) 的.

瓶颈在第二种转移上，先添加一个左括号，再添加一个右括号，这样分步扩展 .

此时，需新建一个状态 \(g(i,j)\) 表示从节点 \(i\) 到节点 \(j\) 合法串再带一个左括号的最小代价 .

这样，第一个转移不变，第二个转移变成，\(f(k,j)=f(i,j)+w(k,j)\)

对于 \(g(i,j)\) 的转移是, \(f(i,k)=g(i,j)+w(k,j)\) .

这样，拆成了两个 \(\mathrm O(m)\) 的 .

实现的时候把 \(f\) 和 \(g\) 放在一个 priority_queue 里，时间复杂度是 \(\mathrm O((n^3+nm)\log n^2)\) 的.

理论上可以，但是我人傻常数大，所以就 t 了 .

可以考虑，这种转移是边比较多，用 priority_queue 可能别多次加入，不划算，用 spfa 更好一些 ，或者是自己手写堆 .

时间复杂度 : \(\mathrm O(k(n^3+nm))\)

空间复杂度 : \(\mathrm O(n^2+m)\)

code

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	int res=0;
	while(ch>='0'&&ch<='9'){
		res=(res<<3)+(res<<1)+ch-'0';
		ch=getchar();
	}
	return res;
}
inline void print(int res){
	if(res==0){
		putchar('0');
		return;
	}
	int a[10],len=0;
	while(res>0){
		a[len++]=res%10;
		res/=10;
	}
	for(int i=len-1;i>=0;i--)
		putchar(a[i]+'0');
}
const long long inf=1e18+10;
const int mod=998244353;
int n,m,q;
vector<pair<int,int> >nei[405][2],rnei[405][2];
long long f[405][405],g[405][405];
bool vis[405][405][2];
queue<pair<bool,pair<int,int> > >que;
int main(){
	freopen("distant.in","r",stdin);
	freopen("distant.out","w",stdout);
	n=read();m=read();q=read();
	for(int i=0;i<m;i++){
		int u=read()-1,v=read()-1,w=read(),t=read()-1;
		nei[u][t].push_back(make_pair(v,w));
		rnei[v][t].push_back(make_pair(u,w));
	}
	for(int i=0;i<n;i++)for(int j=0;j<n;j++){
		f[i][j]=g[i][j]=inf;
	}
	for(int i=0;i<n;i++){
		f[i][i]=0;
		vis[i][i][0]=true;
		que.push(make_pair(0,make_pair(i,i)));
	}
	while(!que.empty()){
		int t=que.front().first;
		int u=que.front().second.first,v=que.front().second.second;
		que.pop();
		vis[u][v][t]=false;
		if(t==0){
			for(int i=0;i<n;i++){
				if(f[u][i]>f[u][v]+f[v][i]){
					f[u][i]=f[u][v]+f[v][i];
					if(!vis[u][i][0]){
						vis[u][i][0]=true;
						que.push(make_pair(0,make_pair(u,i)));
					}
				}
				if(f[i][v]>f[i][u]+f[u][v]){
					f[i][v]=f[i][u]+f[u][v];
					if(!vis[i][v][0]){
						vis[i][v][0]=true;
						que.push(make_pair(0,make_pair(i,v)));
					}
				}
			}
			for(int i=0;i<(int)rnei[u][0].size();i++){
				int to=rnei[u][0][i].first,w=rnei[u][0][i].second;
				if(g[to][v]>f[u][v]+w){
					g[to][v]=f[u][v]+w;
					if(!vis[to][v][1]){
						vis[to][v][1]=true;
						que.push(make_pair(1,make_pair(to,v)));
					}
				}
			}
		}
		else{
			for(int i=0;i<(int)nei[v][1].size();i++){
				int to=nei[v][1][i].first,w=nei[v][1][i].second;
				if(f[u][to]>g[u][v]+w){
					f[u][to]=g[u][v]+w;
					if(!vis[u][to][0]){
						vis[u][to][0]=true;
						que.push(make_pair(0,make_pair(u,to)));
					}
				}
			}
		}
	}
	for(int i=0;i<n;i++)for(int j=0;j<n;j++){
		if(f[i][j]==inf)f[i][j]=-1;
		else f[i][j]%=mod;
	}
	for(int i=0;i<q;i++){
		int s=read()-1,t=read()-1;
		if(f[s][t]==-1){
			putchar('-');
			putchar('1');
		}
		else{
			print(f[s][t]);
		}
		putchar('\n');
	}
	return 0;
}
/*inline? ll or int? size? min max?*/