結果

問題 No.1612 I hate Construct a Palindrome
ユーザー 👑 SPD_9X2SPD_9X2
提出日時 2021-07-21 22:52:34
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 449 ms / 2,000 ms
コード長 3,866 bytes
コンパイル時間 157 ms
コンパイル使用メモリ 82,524 KB
実行使用メモリ 142,352 KB
最終ジャッジ日時 2024-07-17 19:56:29
合計ジャッジ時間 8,177 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 37 ms
55,884 KB
testcase_01 AC 63 ms
69,320 KB
testcase_02 AC 276 ms
124,140 KB
testcase_03 AC 37 ms
55,232 KB
testcase_04 AC 58 ms
69,384 KB
testcase_05 AC 279 ms
124,492 KB
testcase_06 AC 331 ms
125,632 KB
testcase_07 AC 320 ms
125,888 KB
testcase_08 AC 319 ms
127,536 KB
testcase_09 AC 260 ms
119,068 KB
testcase_10 AC 259 ms
118,656 KB
testcase_11 AC 266 ms
121,076 KB
testcase_12 AC 277 ms
120,260 KB
testcase_13 AC 281 ms
120,252 KB
testcase_14 AC 290 ms
120,000 KB
testcase_15 AC 445 ms
139,680 KB
testcase_16 AC 449 ms
142,352 KB
testcase_17 AC 427 ms
140,184 KB
testcase_18 AC 54 ms
66,444 KB
testcase_19 AC 53 ms
65,924 KB
testcase_20 AC 52 ms
65,492 KB
testcase_21 AC 59 ms
69,028 KB
testcase_22 AC 58 ms
68,936 KB
testcase_23 AC 58 ms
69,456 KB
testcase_24 AC 58 ms
70,176 KB
testcase_25 AC 57 ms
70,460 KB
testcase_26 AC 57 ms
71,436 KB
testcase_27 AC 39 ms
55,684 KB
testcase_28 AC 39 ms
55,548 KB
testcase_29 AC 38 ms
54,516 KB
testcase_30 AC 39 ms
55,728 KB
testcase_31 AC 39 ms
55,444 KB
testcase_32 AC 38 ms
55,480 KB
testcase_33 AC 39 ms
55,868 KB
testcase_34 AC 39 ms
56,316 KB
testcase_35 AC 39 ms
54,868 KB
testcase_36 AC 37 ms
54,580 KB
testcase_37 AC 40 ms
55,556 KB
testcase_38 AC 37 ms
55,776 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