山遥路远
山遥路远
题面：
? 给你一个 \(n\) 个点，\(m\) 条边的有向图，每条有向边有一个长度 \(w\)，且上面有一个字符，这个字符只可能是左括号或者右括号，即 \((\) 或 \()\)。
? 我们称一条路径是合法路径，满足其经过的所有字符拼接起来得到的括号串是一 个合法括号序列。 接下来有 \(q\) 组询问，每次询问给出节点 \(s\),\(t\)，问 \(s\) 到 \(t\) 是否存在一条合法路径，如 果存在，那么请输出其最短合法路径的长度。由于答案可能很大，你只需要输出答案模 \(998244353\) 的结果。
? 注意这个图可能有重边和自环。
考虑求出 \(f_{i,j}\) 表示满足从 \(i\) 到 \(j\) 最短的合法路径长度。
易知括号序列的组成应该有两种情况：
- 括号序列仅由若干合法括号序列拼接而成。
- 括号序列开头和末尾有若干个匹配括号，中间为拼接。
容易想到的想法是先求出第二个在求出第一个。实际上这种做法是假的，这两种情况是相辅相成的。也就是可能是由 \(1\) 情况拼接成的 \(2\) 情况括号外边再套几个括号又成为 \(1\) 情况。所以我们是不能分开做的，而应该互相更新。
而更新可以使用一种基于 dij 的贪心。
我们用堆来维护 \(f_{i,j}\)，每次取出一个最小的 \(f_{i,j}\)，并且分别基于上面两种情况更新：
- 在左端点和右端点分别枚举边 \(e,g\)，且 \(e\) 上字符为 \((\)，\(g\) 上字符为 \()\)。
- 枚举一个点 \(x\)，用 \(f_{i.j}+f_{j,x}\) 或者 \(f_{x,i}+f_{i,j}\) 更新 \(f_{i,x}\) 与 \(f_{x,j}\)。
那么复杂度是 \(O((m^2+n^3)\times\log n)\)的。期望得分 \(80\)。
考虑优化枚举两条边的复杂度。我们可以再开一维状态。\(f_{i,j,0/1}\) 表示从 \(i\) 到 \(j\) 的最短路径，左边是否恰好多出一个左括号。
那么我们分开转移，对于 \(f_{i,j,0}\) 我们枚举点和一条边转移。对于 \(f_{i,j,1}\) 我们也枚举一条边转移。
那么复杂度就降到了 \(O((n\times m+n^3)\times\log n\)。
代码如下：
#include
#define ll long long
using namespace std;
const ll INF = 1e17;
const int MAXN = 405;
const int MOD = 998244353;
bool Small;
int n,m,q;
ll dis[MAXN][MAXN][2];
struct E
{
int to;ll w;
};
vector e[MAXN],g[MAXN];
bool Sunny;
struct node
{
int u,v,opt;ll w;
bool operator < (const node&x)const
{
return w>x.w;
}
};
void dij()
{
priority_queue q;
for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) dis[i][j][0]=dis[i][j][1]=INF;
for(int i=1;i<=n;++i)
{
dis[i][i][0]=0;
q.push(node{i,i,0,0});
}
while(!q.empty())
{
node now=q.top();
q.pop();
int u=now.u,v=now.v,opt=now.opt;
if(now.w>dis[u][v][opt]) continue;
if(opt==0)
{
for(int i=1;i<=n;++i)
{
if(dis[i][v][0]>dis[u][v][0]+dis[i][u][0])
{
dis[i][v][0]=dis[u][v][0]+dis[i][u][0];
q.push(node{i,v,0,dis[i][v][0]});
}
if(dis[u][i][0]>dis[u][v][0]+dis[v][i][0])
{
dis[u][i][0]=dis[u][v][0]+dis[v][i][0];
q.push(node{u,i,0,dis[u][i][0]});
}
}
for(int i=0;idis[u][v][0]+w)
{
dis[to][v][1]=dis[u][v][0]+w;
q.push(node{to,v,1,dis[to][v][1]});
}
}
}
else
{
for(int i=0;idis[u][v][1]+w)
{
dis[u][tv][0]=dis[u][v][1]+w;
q.push(node{u,tv,0,dis[u][tv][0]});
}
}
}
}
}
int main()
{
// cout<<1.0*(&Sunny-&Small)/1024/1024<<"MB"<=INF?-1:dis[u][v][0]%MOD);
}
return 0;
}