結果

問題 No.1612 I hate Construct a Palindrome
コンテスト
ユーザー 👑 SPD_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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

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