Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], skipTags: ["script","noscript","style","textarea","code"], processEscapes: true }});

Problem F
  Pizza Delivery
  

  Alyssa is a college student, living in New Tsukuba City. All the streets in the city are one-way. A new social experiment starting tomorrow is on alternative traffic regulation reversing the one-way directions of street sections. Reversals will be on one single street section between two adjacent intersections for each day; the directions of all the other sections will not change, and the reversal will be canceled on the next day.

Alyssa orders a piece of pizza everyday from the same pizzeria. The pizza is delivered along the shortest route from the intersection with the pizzeria to the intersection with Alyssa's house.

  Altering the traffic regulation may change the shortest route. Please tell Alyssa how the social experiment will affect the pizza delivery route.

Input

  The input consists of a single test case in the following format.

$n$ $m$
$a_1$ $b_1$ $c_1$
...
$a_m$ $b_m$ $c_m$

  The first line contains two integers, $n$, the number of intersections, and $m$, the number of street sections in New Tsukuba City ($2 \leq n \leq 100 000, 1 \leq m \leq 100 000$). The intersections are numbered $1$ through $n$ and the street sections are numbered $1$ through $m$.

  The following $m$ lines contain the information about the street sections, each with three integers $a_i$, $b_i$, and $c_i$ ($1 \leq a_i  n, 1 \leq b_i \leq n, a_i \ne b_i, 1 \leq c_i \leq 100 000$). They mean that the street section numbered $i$ connects two intersections with the one-way direction from $a_i$ to $b_i$, which will be reversed on the $i$-th day. The street section has the length of $c_i$. Note that there may be more than one street section connecting the same pair of intersections.

  The pizzeria is on the intersection 1 and Alyssa's house is on the intersection 2. It is guaranteed that at least one route exists from the pizzeria to Alyssa's before the social experiment starts.

Output

  The output should contain $m$ lines. The $i$-th line should be

 HAPPY if the shortest route on the $i$-th day will become shorter,

 SOSO if the length of the shortest route on the $i$-th day will not change, and

 SAD if the shortest route on the $i$-th day will be longer or if there will be no route from the pizzeria to Alyssa's house.

  Alyssa doesn't mind whether the delivery bike can go back to the pizzeria or not.

Sample Input 1

4 5
1 3 5
3 4 6
4 2 7
2 1 18
2 3 12

Sample Output 1

SAD
SAD
SAD
SOSO
HAPPY

Sample Input 2

7 5
1 3 2
1 6 3
4 2 4
6 2 5
7 5 6

Sample Output 2

SOSO
SAD
SOSO
SAD
SOSO

Sample Input 3

10 14
1 7 9
1 8 3
2 8 4
2 6 11
3 7 8
3 4 4
3 2 1
3 2 7
4 8 4
5 6 11
5 8 12
6 10 6
7 10 8
8 3 6

Sample Output 3

SOSO
SAD
HAPPY
SOSO
SOSO
SOSO
SAD
SOSO
SOSO
SOSO
SOSO
SOSO
SOSO
SAD



Sample input:
4 5
1 3 5
3 4 6
4 2 7
2 1 18
2 3 12


Sample output:
SAD
SAD
SAD
SOSO
HAPPY

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
from collections import deque
import sys
sys.setrecursionlimit(10**6)
n, m = map(int, input().split())
E = []
G = [[] for i in range(n)]
RG = [[] for i in range(n)]
for i in range(m):
    a, b, c = map(int, input().split())
    E.append((a-1, b-1, c))
    G[a-1].append((b-1, c, i))
    RG[b-1].append((a-1, c, i))
def dijkstra(G, s):
    dist = [10**18]*n
    dist[s] = 0
    que = [(0, s)]
    while que:
        co, v = heappop(que)
        if dist[v] < co:
            continue
        for w, c, i in G[v]:
            if co + c < dist[w]:
                dist[w] = co + c
                heappush(que, (co + c, w))
    return dist
D = dijkstra(G, 0)
RD = dijkstra(RG, 1)

exit(0)

G0 = [[] for i in range(n)]
used = set([1])
deq = deque([1])
P = set()
while deq:
    v = deq.popleft()
    for w, c, i in RG[v]:
        if D[w] + c == D[v]:
            P.add(i)
            if w not in used:
                used.add(w)
                deq.append(w)
            G0[v].append((w, i))
            G0[w].append((v, i))

def bridge(G, N):
    result = set()
    label = [None]*N
    gen = 0
    cost = [0]*N
    def dfs(u, p, i):
        nonlocal gen
        res = 0
        p_cnt = 0
        for v, j in G[u]:
            if v == p:
                p_cnt += 1
                continue
            if label[v] is not None:
                if label[v] < label[u]:
                    cost[v] += 1
                    res += 1
            else:
                label[v] = gen; gen += 1
                res += dfs(v, u, j)
        res -= cost[u]
        if res == 0 and p != -1 and p_cnt == 1:
            result.add(i)
        return res
    dfs(0, -1, None)
    return result
PB = bridge(G0, n)

ans = []
for i in range(m):
    if i in P:
        if i in PB:
            ans.append("SAD")
        else:
            ans.append("SOSO")
    else:
        a, b, c = E[i]
        if D[b] + c + RD[a] < D[1]:
            ans.append("HAPPY")
        else:
            ans.append("SOSO")
print(*ans, sep='\n')

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
from collections import deque
import sys
sys.setrecursionlimit(10**6)
n, m = map(int, input().split())
E = []
G = [[] for i in range(n)]
RG = [[] for i in range(n)]
for i in range(m):
    a, b, c = map(int, input().split())
    E.append((a-1, b-1, c))
    G[a-1].append((b-1, c, i))
    RG[b-1].append((a-1, c, i))
def dijkstra(G, s):
    dist = [10**18]*n
    dist[s] = 0
    que = [(0, s)]
    while que:
        co, v = heappop(que)
        if dist[v] < co:
            continue
        for w, c, i in G[v]:
            if co + c < dist[w]:
                dist[w] = co + c
                heappush(que, (co + c, w))
    return dist
D = dijkstra(G, 0)
RD = dijkstra(RG, 1)

G0 = [[] for i in range(n)]
used = set([1])
deq = deque([1])
P = set()
while deq:
    v = deq.popleft()
    for w, c, i in RG[v]:
        if D[w] + c == D[v]:
            P.add(i)
            if w not in used:
                used.add(w)
                deq.append(w)
            G0[v].append((w, i))
            G0[w].append((v, i))

PB = set()
label = [None]*n
gen = 0
cost = [0]*n
def dfs(u, p, i):
    global gen
    res = 0
    p_cnt = 0
    for v, j in G0[u]:
        if v == p:
            p_cnt += 1
            continue
        if label[v] is not None:
            if label[v] < label[u]:
                cost[v] += 1
                res += 1
        else:
            label[v] = gen; gen += 1
            res += dfs(v, u, j)
    res -= cost[u]
    if res == 0 and p != -1 and p_cnt == 1:
        PB.add(i)
    return res
dfs(0, -1, None)

ans = []
for i in range(m):
    if i in P:
        if i in PB:
            ans.append("SAD")
        else:
            ans.append("SOSO")
    else:
        a, b, c = E[i]
        if D[b] + c + RD[a] < D[1]:
            ans.append("HAPPY")
        else:
            ans.append("SOSO")
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import deque
import sys
sys.setrecursionlimit(10**6)
n, m = map(int, input().split())
E = []
G = [[] for i in range(n)]
RG = [[] for i in range(n)]
for i in range(m):
    a, b, c = map(int, input().split())
    E.append((a-1, b-1, c))
    G[a-1].append((b-1, c, i))
    RG[b-1].append((a-1, c, i))
def dijkstra(G, s):
    dist = [10**18]*n
    dist[s] = 0
    que = [(0, s)]
    while que:
        co, v = heappop(que)
        if dist[v] < co:
            continue
        for w, c, i in G[v]:
            if co + c < dist[w]:
                dist[w] = co + c
                heappush(que, (co + c, w))
    return dist
D = dijkstra(G, 0)
RD = dijkstra(RG, 1)

G0 = [[] for i in range(n)]
used = set([1])
deq = deque([1])
P = set()
while deq:
    v = deq.popleft()
    for w, c, i in RG[v]:
        if D[w] + c == D[v]:
            P.add(i)
            if w not in used:
                used.add(w)
                deq.append(w)
            G0[v].append((w, i))
            G0[w].append((v, i))

PB = set()
label = [None]*n
gen = 1
cost = [0]*n
def dfs(u, p, i):
    global gen
    res = 0
    p_cnt = 0
    for v, j in G0[u]:
        if v == p:
            p_cnt += 1
            continue
        if label[v] is not None:
            if label[v] < label[u]:
                cost[v] += 1
                res += 1
        else:
            label[v] = gen; gen += 1
            res += dfs(v, u, j)
    res -= cost[u]
    if res == 0 and p != -1 and p_cnt == 1:
        PB.add(i)
    return res
label[0] = 0
dfs(0, -1, None)

ans = []
for i in range(m):
    if i in P:
        if i in PB:
            ans.append("SAD")
        else:
            ans.append("SOSO")
    else:
        a, b, c = E[i]
        if D[b] + c + RD[a] < D[1]:
            ans.append("HAPPY")
        else:
            ans.append("SOSO")
print(*ans, sep='\n')

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop
from collections import deque
import sys
sys.setrecursionlimit(10**6)
n, m = map(int, input().split())
E = []
G = [[] for i in range(n)]
RG = [[] for i in range(n)]
for i in range(m):
    a, b, c = map(int, input().split())
    E.append((a-1, b-1, c))
    G[a-1].append((b-1, c, i))
    RG[b-1].append((a-1, c, i))
def dijkstra(G, s):
    dist = [10**18]*n
    dist[s] = 0
    que = [(0, s)]
    while que:
        co, v = heappop(que)
        if dist[v] < co:
            continue
        for w, c, i in G[v]:
            if co + c < dist[w]:
                dist[w] = co + c
                heappush(que, (co + c, w))
    return dist
D = dijkstra(G, 0)
RD = dijkstra(RG, 1)

G0 = [[] for i in range(n)]
used = set([1])
deq = deque([1])
P = set()
while deq:
    v = deq.popleft()
    for w, c, i in RG[v]:
        # w --> v
        if D[w] + c == D[v]:
            P.add(i)
            if w not in used:
                used.add(w)
                deq.append(w)
            G0[v].append((w, i))
            G0[w].append((v, i))

def bridge(G, N):
    result = set()
    label = [None]*N
    gen = 0
    cost = [0]*N
    def dfs(u, p, i):
        nonlocal gen
        res = 0
        p_cnt = 0
        for v, j in G[u]:
            if v == p:
                p_cnt += 1
                continue
            if label[v] is not None:
                if label[v] < label[u]:
                    cost[v] += 1
                    res += 1
            else:
                label[v] = gen; gen += 1
                res += dfs(v, u, j)
        res -= cost[u]
        if res == 0 and p != -1 and p_cnt == 1:
            result.add(i)
        return res
    dfs(v, -1, None)
    return result
PB = bridge(G0, n)

ans = []
for i in range(m):
    if i in P:
        if i in PB:
            ans.append("SAD")
        else:
            ans.append("SOSO")
    else:
        a, b, c = E[i]
        if D[b] + c + RD[a] < D[1]:
            ans.append("HAPPY")
        else:
            ans.append("SOSO")
*_,=map(print, ans)

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop
from collections import deque
import sys
sys.setrecursionlimit(10**6)
n, m = map(int, input().split())
E = []
G = [[] for i in range(n)]
RG = [[] for i in range(n)]
for i in range(m):
    a, b, c = map(int, input().split())
    E.append((a-1, b-1, c))
    G[a-1].append((b-1, c, i))
    RG[b-1].append((a-1, c, i))
def dijkstra(G, s):
    dist = [10**18]*n
    dist[s] = 0
    que = [(0, s)]
    while que:
        co, v = heappop(que)
        if dist[v] < co:
            continue
        for w, c, i in G[v]:
            if co + c < dist[w]:
                dist[w] = co + c
                heappush(que, (co + c, w))
    return dist
D = dijkstra(G, 0)
RD = dijkstra(RG, 1)

G0 = [[] for i in range(n)]
used = set([1])
deq = deque([1])
P = set()
while deq:
    v = deq.popleft()
    for w, c, i in RG[v]:
        if D[w] + c == D[v]:
            P.add(i)
            if w not in used:
                used.add(w)
                deq.append(w)
            G0[v].append((w, i))
            G0[w].append((v, i))

def bridge(G, N):
    result = set()
    label = [None]*N
    gen = 0
    cost = [0]*N
    def dfs(u, p, i):
        nonlocal gen
        res = 0
        p_cnt = 0
        for v, j in G[u]:
            if v == p:
                p_cnt += 1
                continue
            if label[v] is not None:
                if label[v] < label[u]:
                    cost[v] += 1
                    res += 1
            else:
                label[v] = gen; gen += 1
                res += dfs(v, u, j)
        res -= cost[u]
        if res == 0 and p != -1 and p_cnt == 1:
            result.add(i)
        return res
    dfs(v, -1, None)
    return result
PB = bridge(G0, n)

ans = []
for i in range(m):
    if i in P:
        if i in PB:
            ans.append("SAD")
        else:
            ans.append("SOSO")
    else:
        a, b, c = E[i]
        if D[b] + c + RD[a] < D[1]:
            ans.append("HAPPY")
        else:
            ans.append("SOSO")
print(*ans, sep='\n')

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop
from collections import deque
import sys
sys.setrecursionlimit(10**6)
n, m = map(int, input().split())
E = []
G = [[] for i in range(n)]
RG = [[] for i in range(n)]
for i in range(m):
    a, b, c = map(int, input().split())
    E.append((a-1, b-1, c))
    G[a-1].append((b-1, c, i))
    RG[b-1].append((a-1, c, i))
def dijkstra(G, s):
    dist = [10**18]*n
    dist[s] = 0
    que = [(0, s)]
    while que:
        co, v = heappop(que)
        if dist[v] < co:
            continue
        for w, c, i in G[v]:
            if co + c < dist[w]:
                dist[w] = co + c
                heappush(que, (co + c, w))
    return dist
D = dijkstra(G, 0)
RD = dijkstra(RG, 1)

G0 = [[] for i in range(n)]
used = set([1])
deq = deque([1])
P = set()
while deq:
    v = deq.popleft()
    for w, c, i in RG[v]:
        if D[w] + c == D[v]:
            P.add(i)
            if w not in used:
                used.add(w)
                deq.append(w)
            G0[v].append((w, i))
            G0[w].append((v, i))

def bridge(G, N):
    result = set()
    label = [None]*N
    gen = 0
    cost = [0]*N
    def dfs(u, p, i):
        nonlocal gen
        res = 0
        p_cnt = 0
        for v, j in G[u]:
            if v == p:
                p_cnt += 1
                continue
            if label[v] is not None:
                if label[v] < label[u]:
                    cost[v] += 1
                    res += 1
            else:
                label[v] = gen; gen += 1
                res += dfs(v, u, j)
        res -= cost[u]
        if res == 0 and p != -1 and p_cnt == 1:
            result.add(i)
        return res
    dfs(0, -1, None)
    return result
PB = bridge(G0, n)

ans = []
for i in range(m):
    if i in P:
        if i in PB:
            ans.append("SAD")
        else:
            ans.append("SOSO")
    else:
        a, b, c = E[i]
        if D[b] + c + RD[a] < D[1]:
            ans.append("HAPPY")
        else:
            ans.append("SOSO")
print(*ans, sep='\n')

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop
from collections import deque
import sys
sys.setrecursionlimit(5*10**5)
n, m = map(int, input().split())
E = []
G = [[] for i in range(n)]
RG = [[] for i in range(n)]
for i in range(m):
    while 1:
        try:
            a, b, c = map(int, input().split())
            break
        except: pass
    E.append((a-1, b-1, c))
    G[a-1].append((b-1, c, i))
    RG[b-1].append((a-1, c, i))
def dijkstra(G, s):
    dist = [10**18]*n
    dist[s] = 0
    que = [(0, s)]
    while que:
        co, v = heappop(que)
        if dist[v] < co:
            continue
        for w, c, i in G[v]:
            if co + c < dist[w]:
                dist[w] = co + c
                heappush(que, (co + c, w))
    return dist
D = dijkstra(G, 0)
RD = dijkstra(RG, 1)

G0 = [[] for i in range(n)]
used = set([1])
deq = deque([1])
P = set()
while deq:
    v = deq.popleft()
    for w, c, i in RG[v]:
        if D[w] + c == D[v]:
            P.add(i)
            if w not in used:
                used.add(w)
                deq.append(w)
            G0[v].append((w, i))
            G0[w].append((v, i))

def bridge(G, N):
    result = set()
    label = [None]*N
    gen = 0
    cost = [0]*N
    def dfs(u, p, i):
        nonlocal gen
        res = 0
        p_cnt = 0
        for v, j in G[u]:
            if v == p:
                p_cnt += 1
                continue
            if label[v] is not None:
                if label[v] < label[u]:
                    cost[v] += 1
                    res += 1
            else:
                label[v] = gen; gen += 1
                res += dfs(v, u, j)
        res -= cost[u]
        if res == 0 and p != -1 and p_cnt == 1:
            result.add(i)
        return res
    dfs(0, -1, None)
    return result
PB = bridge(G0, n)

ans = []
for i in range(m):
    if i in P:
        if i in PB:
            ans.append("SAD")
        else:
            ans.append("SOSO")
    else:
        a, b, c = E[i]
        if D[b] + c + RD[a] < D[1]:
            ans.append("HAPPY")
        else:
            ans.append("SOSO")
print(*ans, sep='\n')

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop
from collections import deque
import sys
sys.setrecursionlimit(10**6)
*ipts, = map(int, open(0).read().split())
n, m = ipts[:2]
#n, m = map(int, input().split())
E = []
G = [[] for i in range(n)]
RG = [[] for i in range(n)]
for i in range(m):
    #a, b, c = map(int, input().split())
    a, b, c = ipts[2+3*i:5+3*i]
    E.append((a-1, b-1, c))
    G[a-1].append((b-1, c, i))
    RG[b-1].append((a-1, c, i))
def dijkstra(G, s):
    dist = [10**18]*n
    dist[s] = 0
    que = [(0, s)]
    while que:
        co, v = heappop(que)
        if dist[v] < co:
            continue
        for w, c, i in G[v]:
            if co + c < dist[w]:
                dist[w] = co + c
                heappush(que, (co + c, w))
    return dist
D = dijkstra(G, 0)
RD = dijkstra(RG, 1)

G0 = [[] for i in range(n)]
used = set([1])
deq = deque([1])
P = set()
while deq:
    v = deq.popleft()
    for w, c, i in RG[v]:
        if D[w] + c == D[v]:
            P.add(i)
            if w not in used:
                used.add(w)
                deq.append(w)
            G0[v].append((w, i))
            G0[w].append((v, i))

def bridge(G, N):
    result = set()
    label = [None]*N
    gen = 0
    cost = [0]*N
    def dfs(u, p, i):
        nonlocal gen
        res = 0
        p_cnt = 0
        for v, j in G[u]:
            if v == p:
                p_cnt += 1
                continue
            if label[v] is not None:
                if label[v] < label[u]:
                    cost[v] += 1
                    res += 1
            else:
                label[v] = gen; gen += 1
                res += dfs(v, u, j)
        res -= cost[u]
        if res == 0 and p != -1 and p_cnt == 1:
            result.add(i)
        return res
    dfs(0, -1, None)
    return result
PB = bridge(G0, n)

ans = []
for i in range(m):
    if i in P:
        if i in PB:
            ans.append("SAD")
        else:
            ans.append("SOSO")
    else:
        a, b, c = E[i]
        if D[b] + c + RD[a] < D[1]:
            ans.append("HAPPY")
        else:
            ans.append("SOSO")
print(*ans, sep='\n')