luogu#P11938. [CrCPC 2024] 信步山中

[CrCPC 2024] 信步山中

题目背景

译自 Natjecanje timova studenata informatičara hrvatskih sveučilišta H.

题目描述

给定两张 nn 个点的无向连通图 G1(V1,E1),G2(V2,E2)G_1(V_1,E_1),G_2(V_2,E_2)。边有边权。

初始时童子军们在起点 ss,他们要行军到终点 tt

他们的行动会遵循以下规则:

令童子军当前在节点 xx

  • 1,3,5,1,3,5,\cdots 次移动,他们会选择一条边 (x,y,w)E1(x,y,w)\in E_1,然后移动到 yy
    • dist1(x,y)\operatorname{dist}_1(x,y) 表示 G1G_1x,yx,y 之间的最短路长度。$\operatorname{dist}_1(x,t)\textcolor{red}{\gt}\operatorname{dist}_1(y,t)$ 必须满足。
  • 2,4,6,2,4,6,\cdots 次移动,他们会选择一条边 (x,y,w)E2(x,y,w)\in E_2,然后移动到 yy
    • dist2(x,y)\operatorname{dist}_2(x,y) 表示 G2G_2x,yx,y 之间的最短路长度。$\operatorname{dist}_2(x,t)\textcolor{red}{\gt}\operatorname{dist}_2(y,t)$ 必须满足。

你需要求出,在满足上述条件的情况下,从起点到终点经过边的边权和的最大值

特别地,最大值可以为无穷大,即他们可以永远走不到终点。在符合条件的情况下,可以一直拖着不走到终点。

输入格式

第一行,三个正整数 n,s,tn,s,t

第二行,一个正整数 m1m_1,表示 G1G_1 的边数 E1|E_1|

接下来 m1m_1 行,每行三个正整数 u,v,wu,v,w,表示 (u,v,w)E1(u,v,w)\in E_1

(m1+3)(m_1+3) 行,一个正整数 m2m_2,表示 G2G_2 的边数 E2|E_2|

接下来 m2m_2 行,每行三个正整数 u,v,wu,v,w,表示 (u,v,w)E2(u,v,w)\in E_2

输出格式

如果答案为无穷大,输出一行一个 -1\texttt{-1}

否则输出一行一个非负整数表示答案。

5 1 5
5
1 2 2
1 4 2
2 3 1
3 4 1
5 3 1
4
1 2 2
2 4 2
2 3 1
2 5 2
-1
3 1 3
4
1 2 10
2 3 10
1 3 20
2 3 30
4
2 1 10
1 3 10
1 1 10
2 3 10
20

提示

  • 2n1032\le n\le 10^3
  • n1m1,m2105n-1\le m_1,m_2\le 10^5
  • 1u,vn1\le u,v\le n1w1061\le w\le 10^6
  • 1s,tn1\le s,t\le n