結果

問題 No.1612 I hate Construct a Palindrome
ユーザー 👑 SPD_9X2SPD_9X2
提出日時 2021-07-21 22:52:34
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 624 ms / 2,000 ms
コード長 3,866 bytes
コンパイル時間 346 ms
コンパイル使用メモリ 87,216 KB
実行使用メモリ 144,148 KB
最終ジャッジ日時 2023-09-24 19:13:09
合計ジャッジ時間 13,359 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 102 ms
71,612 KB
testcase_01 AC 123 ms
77,808 KB
testcase_02 AC 382 ms
122,168 KB
testcase_03 AC 96 ms
71,452 KB
testcase_04 AC 120 ms
77,576 KB
testcase_05 AC 381 ms
121,860 KB
testcase_06 AC 432 ms
128,884 KB
testcase_07 AC 451 ms
126,084 KB
testcase_08 AC 445 ms
126,488 KB
testcase_09 AC 391 ms
123,928 KB
testcase_10 AC 392 ms
122,940 KB
testcase_11 AC 387 ms
120,624 KB
testcase_12 AC 392 ms
123,148 KB
testcase_13 AC 414 ms
124,448 KB
testcase_14 AC 407 ms
124,124 KB
testcase_15 AC 605 ms
143,288 KB
testcase_16 AC 624 ms
142,356 KB
testcase_17 AC 599 ms
144,148 KB
testcase_18 AC 111 ms
77,912 KB
testcase_19 AC 109 ms
77,612 KB
testcase_20 AC 109 ms
77,576 KB
testcase_21 AC 116 ms
78,192 KB
testcase_22 AC 120 ms
78,192 KB
testcase_23 AC 118 ms
78,140 KB
testcase_24 AC 119 ms
78,040 KB
testcase_25 AC 119 ms
78,152 KB
testcase_26 AC 115 ms
78,204 KB
testcase_27 AC 95 ms
71,900 KB
testcase_28 AC 96 ms
71,408 KB
testcase_29 AC 97 ms
71,664 KB
testcase_30 AC 96 ms
71,688 KB
testcase_31 AC 99 ms
71,572 KB
testcase_32 AC 95 ms
71,828 KB
testcase_33 AC 95 ms
71,608 KB
testcase_34 AC 96 ms
71,412 KB
testcase_35 AC 96 ms
71,808 KB
testcase_36 AC 98 ms
71,688 KB
testcase_37 AC 95 ms
71,748 KB
testcase_38 AC 95 ms
71,804 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""

全部が同じ種類の辺なら不可能
そうでないなら、2種類の文字を使うパスを見付ける
あとは、半分を同じ文字で埋める

start が 2色
goal が2色
ならそのうち使われなかった方を繰り返しに採用する

それ以外なら、適当に辺を持ってくる

"""

from sys import stdin
import sys
from collections import deque

N,M = map(int,stdin.readline().split())

#olis = [ [] for i in range(N) ]
lis = [ [] for i in range(N) ]
C = []
AB = []

for i in range(M):

    A,B,tC = stdin.readline().split()
    A = int(A)
    B = int(B)
    tC = ord(tC)

    A -= 1
    B -= 1

    C.append( tC )
    AB.append((A,B))

    lis[A].append( (B,i) )
    lis[B].append( (A,i) )

#2色のパスを見付ける必要がある

Cset = set(C)
if len(Cset) == 1:
    print (-1)
    sys.exit()

sc = set()
gc = set()

for nex,ind in lis[0]:
    sc.add(C[ind])
for nex,ind in lis[N-1]:
    gc.add(C[ind])

sc = list(sc)
gc = list(gc)

if len(sc) > 1 or len(gc) > 1:

    dlis = [float("inf")] * N
    plis = [i for i in range(N)]
    elis = [None] * N

    q = deque([0])
    dlis[0] = 0

    while q:

        v = q.popleft()
        for nex,ind in lis[v]:
            if dlis[nex] > dlis[v] + 1:
                dlis[nex] = dlis[v] + 1
                plis[nex] = v
                elis[nex] = ind
                q.append(nex)

    ans = []
    nv = N-1

    while nv != 0:
        ans.append( elis[nv] )
        nv = plis[nv]

    if len(sc) > 1:

        fe = None
        for nex,ind in lis[0]:
            if C[ind] != C[ans[-1]]:
                fe = ind
                break

        while len(ans) + 2 <= 2*N:
            ans.append(fe)
            ans.append(fe)

        ans.reverse()
        for i in range(len(ans)):
            ans[i] += 1

        print (len(ans))
        print ("\n".join(map(str,ans)))
        sys.exit()

    else:

        ge = None
        ans.reverse()
        
        for nex,ind in lis[0]:
            if C[ind] != C[ans[-1]]:
                ge = ind
                break

        while len(ans) + 2 <= 2*N:
            ans.append(ge)
            ans.append(ge)

        for i in range(len(ans)):
            ans[i] += 1

        print (len(ans))
        print ("\n".join(map(str,ans)))
        sys.exit()

else:

    lastc = gc[0]
    wante = None

    for i in range(M):
        if C[i] != lastc:
            wante = i
            break

    wA,wB = AB[wante]


    dlis = [float("inf")] * N
    plis = [i for i in range(N)]
    elis = [None] * N
    q = deque([0])
    dlis[0] = 0
    while q:
        v = q.popleft()
        for nex,ind in lis[v]:
            if dlis[nex] > dlis[v] + 1:
                dlis[nex] = dlis[v] + 1
                plis[nex] = v
                elis[nex] = ind
                q.append(nex)

    zlast = wA if dlis[wA] < dlis[wB] else wB
    zans = []

    nv = zlast
    while nv != 0:
        zans.append(elis[nv])
        nv = plis[nv]

    zans.reverse()
    


    dlis = [float("inf")] * N
    plis = [i for i in range(N)]
    elis = [None] * N
    q = deque([N-1])
    dlis[N-1] = 0
    while q:
        v = q.popleft()
        for nex,ind in lis[v]:
            if dlis[nex] > dlis[v] + 1:
                dlis[nex] = dlis[v] + 1
                plis[nex] = v
                elis[nex] = ind
                q.append(nex)

    nlast = wA if dlis[wA] < dlis[wB] else wB
    nans = []

    nv = nlast
    while nv != N-1:
        nans.append(elis[nv])
        nv = plis[nv]

    if zlast == nlast:
        zans.append(wante)
        zans.append(wante)
    else:
        zans.append(wante)

    ans = zans + nans

    while len(ans) + 2 <= 2*N:
        ans.append(lis[N-1][0][1])
        ans.append(ans[-1])

    for i in range(len(ans)):
        ans[i] += 1
    print (len(ans))
    print ("\n".join(map(str,ans)))
    sys.exit()
0