Submission #38811433

---

Source Code Expand

from collections import defaultdict
import heapq
T,=map(int,input().split())

K = 2001

def solve():
    N,M=map(int,input().split())
    cl = list(map(int, input().split()))

    edges = defaultdict(list)
    for _ in range(M):
        u, v = map(int,input().split())
        edges[u-1].append(v-1)
        edges[v-1].append(u-1)
    
    costs = [100000000]*(N*K)
    costs[0+(N-1)*K]=0
    queue = []
    visited = set()
    heapq.heappush(queue, (0, 0+(N-1)*K))
    while len(queue) > 0:
        cost, pos = heapq.heappop(queue)
        if pos in visited:
            continue
        visited.add(pos)
        pos0 = pos % K
        pos1 = pos // K
        for pos0t in edges[pos0]:
            for pos1t in edges[pos1]:
                if cl[pos0t] != cl[pos1t]:
                    newcost = cost + 1
                    key = pos0t + pos1t*K
                    lastcost = costs[key]
                    if newcost < lastcost:
                        costs[key] = newcost
                        heapq.heappush(queue, (newcost, key))
    result_cost = costs[N-1+0*K]
    if result_cost >= 100000000:
        result_cost = -1
    print(result_cost)

for _ in range(T):
    solve()

Submission Info

Judge Result