152. Day 4 PD. 重返榮耀

0 Judge

Code: 0


重返榮耀

sprout

題目敘述

運算之星「阿波銳特」中有四家運算器的工廠,分別是負責組裝的 ADD、零件分解的 SUB、模組設計的 MUL 以及回收業者 DIV 。原先 ADD 是阿波銳特裡面最大的工廠,但由於一例一休的影響,ADD 在過去十年間的業績一落千丈,隨時都有倒閉的危險。但最近有消息指出 ADD 運用量子重力以及大強力對撞機,找出了使零件自動組裝的機制,其他三家工廠無不聞之色變,因此他們找了你來想辦法阻止 ADD 重返榮耀。他們想出最好的方法就是阻礙 ADD 零件的運輸。

阿波銳特所在的宇宙是由好幾個星球所共同組成的,有一些星球之間有傳送門可以運輸資源,但是傳送門只能單向地傳輸。阿波銳特的零件都是由星球「破督社」製造,再透過一些傳送門輾轉地運送到阿波銳特。 SUB、MUL跟DIV 從傳送門的製造商那裡拿到了關閉傳送門的機器,能夠讓傳送門暫時無法工作,但關閉的時候需要的一些能量。他們的目標是讓破督社製造的零件無法運到阿波銳特,嚇一嚇 ADD。如果能量使用過多,可能會需要建設新的核電廠,但是他們又希望能建立非核家園,因此需要你告訴他們最少需要使用多少能量。

輸入說明

本題目有多筆測資。

第一行有一個正整數 $T$ 代表測資的數量。

每筆測資的第一行有四個整數 $N, M, x, y$ ,分別代表星球個數、傳送門個數、破督社的星球編號以及阿波銳特的星球編號。

接下來有 $M$ 行,每行有三個整數 $u, v, c$ ,表示有一道從 $u$ 到 $v$ 的傳送門,關閉這道傳送門需要 $c$ 單位的能量。

  • $ 1 \leq T \leq 5 $
  • $ 2 \leq N \leq 100 $, $ 0 \leq M \leq 1,000 $
  • $ 1 \leq x,y \leq N $ 且 $ x \ne y$
  • $ 1 \leq u,v \leq N $, $ 0 \leq c \leq 3,000,000 $

注意:兩個星球之間可能有多個傳送門。

輸出說明

對於每一筆測資,請輸出阻止 ADD 重返榮耀最少需要多少能量。格式參照範例輸出。

範例輸入

2
4 3 1 4
1 2 3
2 3 4
3 4 5
4 4 2 3
2 1 2
2 4 5
1 4 3
4 3 10

範例輸出

3
7

提示

N/A


Judge Setting

run-time limit: 1000 ms
memory limit: 256000000 byte
測資數量: 0