Shortest Path (Codeforces 59E)
Tags: Others, shortest paths

In Ancient Berland there were n cities and m two-way roads of equal length. The cities are numbered with integers from 1 to n inclusively. According to an ancient superstition, if a traveller visits three cities ai, bi, ci in row, without visiting other cities between them, a great disaster awaits him. Overall there are k such city triplets. Each triplet is ordered, which means that, for example, you are allowed to visit the cities in the following order: ai, ci, bi. Vasya wants to get from the city 1 to the city n and not fulfil the superstition. Find out which minimal number of roads he should take. Also you are required to find one of his possible path routes.

Input: The first line contains three integers n, m, k (2 ≤ n ≤ 3000, 1 ≤ m ≤ 20000, 0 ≤ k ≤ 105) which are the number of cities, the number of roads and the number of the forbidden triplets correspondingly. Then follow m lines each containing two integers xi, yi (1 ≤ xi, yi ≤ n) which are the road descriptions. The road is described by the numbers of the cities it joins. No road joins a city with itself, there cannot be more than one road between a pair of cities. Then follow k lines each containing three integers ai, bi, ci (1 ≤ ai, bi, ci ≤ n) which are the forbidden triplets. Each ordered triplet is listed mo more than one time. All three cities in each triplet are distinct.City n can be unreachable from city 1 by roads.

Output: If there are no path from 1 to n print -1. Otherwise on the first line print the number of roads d along the shortest path from the city 1 to the city n. On the second line print d + 1 numbers — any of the possible shortest paths for Vasya. The path should start in the city 1 and end in the city n.


Sample Inputs:
4 4 1
1 2
2 3
3 4
1 3
1 4 3

3 1 0
1 2

4 4 2
1 2
2 3
3 4
1 3
1 2 3
1 3 4

Sample Outputs:
2
1 3 4

-1

4
1 3 2 3 4

Solution (Python):
from collections import defaultdict, deque

def bfs(graph, start, n, mp):
    q = deque([(start, [-1])])
    visited = {}
    while q:
        (cur_node, path) = q.popleft()
        if cur_node == n:
            return path[1:] + [cur_node]
        for neigbour in graph[cur_node]:
            if (cur_node, neigbour) not in visited:
                if (path[-1], cur_node, neigbour) not in mp:
                    q.append([neigbour, path + [cur_node]])
                    visited[cur_node, neigbour] = 1
    return []
(n, m, k) = map(int, input().split())
adj_list = defaultdict(set)
for _ in range(m):
    (u, v) = map(int, input().split())
    adj_list[u].add(v)
    adj_list[v].add(u)
mp = {}
for i in range(k):
    (a, b, c) = map(int, input().split())
    mp[a, b, c] = 1
path = bfs(adj_list, 1, n, mp)
if len(path) > 1:
    print(len(path) - 1)
    print(*path)
else:
    print('-1')

Solution (Python):
class Pathclass:

    def __init__(self, node_number, nextnode):
        self.number = node_number
        self.next = nextnode
import collections
lis = input().split()
(n, m, k) = (int(lis[0]), int(lis[1]), int(lis[2]))
adjlis = [collections.deque([]) for i in range(n)]
for i in range(m):
    lis = input().split()
    (x, y) = (int(lis[0]) - 1, int(lis[1]) - 1)
    adjlis[x].append(y)
    adjlis[y].append(x)
triplet = [[] for i in range(n)]
for i in range(k):
    lis = input().split()
    (a, b, c) = (int(lis[0]) - 1, int(lis[1]) - 1, int(lis[2]) - 1)
    triplet[a].append((b, c))
node_queue = collections.deque([])
path_queue = collections.deque([])
flag = False
pp = Pathclass(0, None)
while adjlis[0]:
    i = adjlis[0].popleft()
    if i == n - 1:
        flag = True
    node_queue.append(i)
    path_queue.append(Pathclass(i, pp))
if flag:
    print(1)
    print(1, n)
else:
    finalpath = None
    while node_queue and (not flag):
        node = node_queue.popleft()
        path = path_queue.popleft()
        lenn = len(adjlis[node])
        for j in range(lenn):
            i = adjlis[node].popleft()
            if not (node, i) in triplet[path.next.number]:
                if i == n - 1:
                    flag = True
                    finalpath = Pathclass(i, path)
                    break
                else:
                    path2 = Pathclass(i, path)
                    node_queue.append(i)
                    path_queue.append(path2)
            else:
                adjlis[node].append(i)
    if not flag:
        print(-1)
    else:
        pathlist = []
        while finalpath:
            pathlist.append(finalpath.number + 1)
            finalpath = finalpath.next
        pathlist.reverse()
        print(len(pathlist) - 1)
        for i in pathlist:
            print(i, end=' ')
        print()

Solution (Python):
def read():
    return map(int, input().split())
(n, m, k) = read()
g = [[] for i in range(n + 2)]
for _ in range(m):
    (u, v) = read()
    g[u].append(v)
    g[v].append(u)
g[n].append(n + 1)
triples = set((a + (b + c * n) * n for (a, b, c) in (read() for i in range(k))))
p = [[-1 for j in range(n + 2)] for i in range(n + 2)]
q = [(0, 1)]
p[0][1] = 0
while q and p[n][n + 1] == -1:
    (w, u) = q.pop(0)
    for v in g[u]:
        if p[u][v] != -1 or w + (u + v * n) * n in triples:
            continue
        p[u][v] = w
        if v == n + 1:
            break
        q.append((u, v))
if p[n][n + 1] != -1:
    ans = []
    (i, j) = (n, n + 1)
    while i:
        ans.append(i)
        (i, j) = (p[i][j], i)
    print(len(ans) - 1)
    print(' '.join(map(str, reversed(ans))))
else:
    print(-1)