結果

問題 No.17 2つの地点に泊まりたい
ユーザー 6soukiti296soukiti29
提出日時 2017-07-26 15:01:29
言語 Nim
(2.0.2)
結果
TLE  
実行時間 -
コード長 1,395 bytes
コンパイル時間 4,507 ms
コンパイル使用メモリ 70,092 KB
実行使用メモリ 4,376 KB
最終ジャッジ日時 2023-09-12 13:36:20
合計ジャッジ時間 10,092 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 TLE -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
/home/judge/data/code/Main.nim(1, 26) Warning: imported and not used: 'math' [UnusedImport]

ソースコード

diff # 

import sequtils,strutils,math
type
    idou = tuple[to : int, cost : int]
var
    N = stdin.readline.parseInt
    S = newSeq[int](0)
    bound = newSeqWith(N,newSeq[idou](0))
    flag = newSeqWith(N,0)
    A,B,C : int
    scost = 0
    ans = high(int)
    miti : seq[int]
for n in 0..<N:
    S.add(stdin.readline.parseInt)
var M = stdin.readline.parseInt
for m in 0..<M:
    (A,B,C) = stdin.readline.split.map(parseInt)
    bound[A].add((B,C))
    bound[B].add((A,C))
    
miti = @[0]

proc tansaku(a : int)=
    if a == N - 1 and miti.len > 3:
        var m1,m2 : int
        var sflag = newSeqWith(N,false)
        for m in miti:
            if m == 0 or m == N - 1 or sflag[m] == true:
                continue
            if m1 == 0:
                m1 = S[m]
            elif m2 == 0:
                m2 = S[m]
                (m1,m2) = (min(m1,m2),max(m1,m2))
            elif m2 > S[m]:
                m2 = S[m]
                (m1,m2) = (min(m1,m2),max(m1,m2))
            sflag[m] = true
        if m1 != 0 and m2 != 0:
            ans = min(ans,scost + m1 + m2)
    else:
        for b in bound[a]:
            if flag[b.to] < 2:
                flag[b.to] += 1
                scost += b.cost
                miti.add(b.to)
                tansaku(b.to)
                discard miti.pop
                flag[b.to] -= 1
                scost -= b.cost

flag[0] = 1
tansaku(0)
echo ans
0