b312. 固有結界
Tags :
Accepted rate : 66人/80人 ( 82% ) [非即時]
評分方式:
Tolerant

最近更新 : 2016-12-18 21:02

Content
固有結界-將想像具象化的奧義,可以將特定範圍內轉變為自己創造的空間。
 
終於只剩下最後兩個Master了,勝利者就可以取的聖杯,並實現願望,但是此時你和你的Servant卻身在固有結界裡(當然,固有結界是對方開的,你根本弱得要死。)。在這個固有結界裡有N個房間,房間跟房間之間有傳送門,每當你的Servant經過傳送門就會被吸收魔力,每個傳送門會吸收的魔力可能不同。敵方Master同樣位於其中一間房間,你必須讓你的Servant前往敵方所在的房間,幹掉他,才能逃出這固有結界並取得最後的勝利。同時你希望被吸收的魔力越少越好,雖然你的Servant很強,但是失去太多魔力也不是好事。你很強的Servant已經感應出每個房間、每個傳送門及通過其會被吸收的魔力還有敵方所在的房間,請用你高中時期學過的程式來算出會被吸走多少魔力吧!!
 
究竟,你會不會取得聖杯,並實現願望呢?
 
Input
第一行有兩個整數N,M,Y,O( 0<N<=5000,0<M<=1000000),N為房間數量(房間編號為1~N),M為傳送門數量,Y是你及你的Servant所在的房間,O是對方所在的房間。
接下來M行每行有三個整數a,b,x表示有一座傳送門連接a房間與b房間(雙向),會吸收x的魔力(0<=x<=1000)。
 
Output
輸出最少會被吸走多少魔力。
(保證一定可以走到敵方房間)
Sample Input #1
7 9 1 7
1 2 2
1 4 3
2 5 2
2 3 3
3 4 4
3 6 1
5 6 3
4 7 5
6 7 1
Sample Output #1
7
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (20%): 10.0s , <1K
公開 測資點#1 (20%): 10.0s , <1K
公開 測資點#2 (20%): 10.0s , <1M
公開 測資點#3 (20%): 10.0s , <1M
公開 測資點#4 (20%): 10.0s , <50M
Hint :
Tags:
出處:
103學年度板橋高中校內資訊學科能力競賽(三) [管理者: snail (蝸牛) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
24767 DE45A (一葉之秋) b312
記憶體只有64MB
542 2021-03-22 22:26