#P10535. [Opoi 2024] 数据转换

[Opoi 2024] 数据转换

题目背景

Arrda 家里面有很多五花八门的用电器和数据线,而且很多用电器的插头种类都不一样,这导致每次 Arrda 想要共享两个用电器的数据时都要一半天用来买到合适的数据线,而且有的时候数据线很贵!

于是 Arrda 想让你求出花钱最少的数据转换方案。

题目描述

Arrda 家中有 nn 类,2n2n 种数据线接头,每一类插头有 22 种不同接头,种类分别为 iin+in+i有且只有同一类的不同接头可以互相连接(你可以理解为 ii 是凸出的接头,n+in + i 是凹的接头,可以连接可以理解为插上)

商城里售卖着 mm 种双向数据线,每根双向数据线两端各有一个接头,种类分别为为 ui,viu_i,v_i。同时,第 ii 种双向数据线有一个购买价格 wiw_i,每种数据线可以购买无限条。

Arrda 想要交换两个用电器的数据,其中两个用电器的接头种类编号为 S,TS,T,求能使这两个用电器能直接或由若干条数据线相连的最小总价格(毕竟买数据线需要钱),如果无解,输出 I have no idea how to solve it.,注意,两个用电器的接口不能直接连接数据线,因为它们在用电器上,而非数据线两端!

输入格式

第一行两个整数 n,mn,m,意义见题面。

接下来 mm 行,每行三个整数 ui,vi,wiu_i,v_i,w_i

接下来一行两个整数 S,TS,T

输出格式

一个非负整数表示能使这两个用电器能直接或由若干条数据线相连的最小总价格。

若无解,请输出 I have no idea how to solve it.

4 4
5 8 10
7 8 2
2 3 1
5 6 5
1 4
8
4 1
2 3 1
1 8
I have no idea how to solve it.
4 1
2 3 1
1 5
0
5 10
1 2 603124134
2 3 373980902
2 4 6578324
3 5 936364479
4 6 182080546
4 7 340293479
6 8 753053273
1 9 274129271
3 10 616764767
4 6 255802600
1 2
3673658542

提示

样例 1 解释:

picture

1=5->6=2->3=7->8=4

可以证明,没有总代价更小的方案。

样例 4 解释

222

1=6->8=3->5=10->3=8->6=1->9=4->7=2

4->6 有两种数据线,我们选择代价为 182080546182080546 的那一根,因为其代价更小。

可以证明,没有总代价更小的方案。

数据范围

对于 100%100\% 的数据,1n,m1051\le n,m \le 10^51ui,vi,s,t2×n1\le u_i,v_i,s,t \le 2 \times n1wi1091\le w_i \le 10^9