Problem:


Score : 500 points

Problem Statement

There are N towns numbered 1 to N and M roads. The i-th road connects Town A_i and Town B_i bidirectionally and has a length of C_i.

Takahashi will travel between these towns by car, passing through these roads. The fuel tank of his car can contain at most L liters of fuel, and one liter of fuel is consumed for each unit distance traveled. When visiting a town while traveling, he can full the tank (or choose not to do so). Travel that results in the tank becoming empty halfway on the road cannot be done.

Process the following Q queries:

The tank is now full. Find the minimum number of times he needs to full his tank while traveling from Town s_i to Town t_i. If Town t_i is unreachable, print -1.

Constraints

All values in input are integers.

2 \leq N \leq 300

0 \leq M \leq \frac{N(N-1)}{2}

1 \leq L \leq 10^9

1 \leq A_i, B_i \leq N

A_i \neq B_i

\left(A_i, B_i\right) \neq \left(A_j, B_j\right) (if i \neq j)

\left(A_i, B_i\right) \neq \left(B_j, A_j\right) (if i \neq j)

1 \leq C_i \leq 10^9

1 \leq Q \leq N\left(N-1\right)

1 \leq s_i, t_i \leq N

s_i \neq t_i

\left(s_i, t_i\right) \neq \left(s_j, t_j\right) (if i \neq j)

Input

Input is given from Standard Input in the following format:

N M L
A_1 B_1 C_1
:
A_M B_M C_M
Q
s_1 t_1
:
s_Q t_Q

Output

Print Q lines.

The i-th line should contain the minimum number of times the tank needs to be fulled while traveling from Town s_i to Town t_i. If Town t_i is unreachable, the line should contain -1 instead.

Sample Input 1

3 2 5
1 2 3
2 3 3
2
3 2
1 3

Sample Output 1

0
1

To travel from Town 3 to Town 2, we can use the second road to reach Town 2 without fueling the tank on the way.

To travel from Town 1 to Town 3, we can first use the first road to get to Town 2, full the tank, and use the second road to reach Town 3.

Sample Input 2

4 0 1
1
2 1

Sample Output 2

-1

There may be no road at all.

Sample Input 3

5 4 4
1 2 2
2 3 2
3 4 3
4 5 2
20
2 1
3 1
4 1
5 1
1 2
3 2
4 2
5 2
1 3
2 3
4 3
5 3
1 4
2 4
3 4
5 4
1 5
2 5
3 5
4 5

Sample Output 3

0
0
1
2
0
0
1
2
0
0
0
1
1
1
0
0
2
2
1
0



Sample input:
3 2 5
1 2 3
2 3 3
2
3 2
1 3


Sample output:
0
1

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import floyd_warshall
import sys
import math
def get_path(start, goal, pred):
    return get_path_row(start, goal, pred[start])

def get_path_row(start, goal, pred_row):
    path = []
    i = goal
    while i != start and i >= 0:
        path.append(i)
        i = pred_row[i]
    if i < 0:
        return []
    path.append(i)
    return path[::-1]

input = sys.stdin.readline
def solve():
  n,m,l = (int(i) for i in input().split())
  path = [[-1*float("Inf")]*n for _ in range(n)]
  for i in range(m):
    a,b,c = (int(i) for i in input().split())
    path[a-1][b-1] = c
    path[b-1][a-1] = c
  d,way = floyd_warshall(path,return_predecessors=True)
  
  q = int(input())
  for i in range(q):
    s,t = (int(i) for i in input().split())
    s,t = s-1,t-1
    tmp = get_path(s,t,way)
    if len(tmp) == 0:
      print(-1)
      continue
    cost = d[s][t]
    can = True
    
    kaisuu = 0
    now = l
    start = s
    for j in range(len(tmp)):
      if not tmp[j] == s:
        tj = tmp[j]
        tmpcost = d[start][tj]
        if tmpcost > l:
          can = False
        else:
          now -= tmpcost
          if now == 0: #補給
            if tmp[j] != t:
              now = l
              kaisuu += 1
          elif now < 0:
            now = l-tmpcost
            kaisuu += 1
          
        start = tj
    if can:
      print(kaisuu)
    else:
      print(-1)
solve()

Submission status: Wrong Answer

Solution code:
#何とか法, AOJのgrl1c
#初め満杯
n,m,l =map(int, input().split( ))
Edge = [[] for _ in range(n)]

for i in range(m):
    a,b,c = map(int, input().split( ))
    Edge[a-1].append([b-1,c])
    Edge[b-1].append([a-1,c])

dp = [[[m+2,10**12] for _ in range(n)] for __ in range(n)]

for i in range(n):
    for ed in Edge[i]:
        if ed[1] <= l:
            dp[i][ed[0]] = [1,ed[1]]

for i in range(n):
    dp[i][i] = [1,0]

for k in range(n):
    for j in range(n):
        for i in range(n):
            f = dp[i][k][0] + dp[k][j][0] - 1
            c = dp[i][k][1] + dp[k][j][1]
            if dp[i][j] > [f,c] and c<=l:
                dp[i][j] = [f,c]
            elif dp[i][j] > [f+1,max(c-l,0)]:###
                dp[i][j] = [f+1,c]###

q = int(input())

for i in range(q):
    s,t = map(int, input().split( ))
    if dp[s-1][t-1][0] >m+1:###
        print(-1)
    else:
        print(dp[s-1][t-1][0]-1)

Submission status: Wrong Answer

Solution code:
import heapq
N,M,L = map(int,input().split())
ABC = [tuple(map(int,input().split())) for i in range(M)]
Q = int(input())
ST = [tuple(map(int,input().split())) for i in range(Q)]

es = [[] for i in range(N)]
for a,b,c in ABC:
    if c > L: continue
    a,b = a-1,b-1
    es[a].append((b,c))
    es[b].append((a,c))

INF = float('inf')
dist = [[INF]*N for i in range(N)]
for i in range(N):
    dist[i][i] = 0

for i in range(N):
    hq = [(0,i)]
    heapq.heapify(hq)
    while hq:
        k,j = heapq.heappop(hq)
        k,l = divmod(k,L)
        for to,c in es[j]:
            if l+c > L:
                newcost = (k+1)*L + c
            else:
                newcost = k*L + l + c
            if newcost < dist[i][to]:
                dist[i][to] = newcost
                heapq.heappush(hq, (newcost, to))

for s,t in ST:
    s,t = s-1,t-1
    print((dist[s][t]-1)//L)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m,L=map(int,input().split())
    A=[[INF]*n for _ in range(n)]
    for _ in range(m):
        a,b,c=map(int,input().split())
        if(c>L): continue
        a-=1; b-=1
        A[a][b]=c
        A[b][a]=c
    # Warshall-Floyd
    from itertools import product
    next=[[0]*n for _ in range(n)]
    for i,j in product(range(n),repeat=2):
        next[i][j]=j
    B=[a[:] for a in A] # deep copy
    for k,i,j in product(range(n),repeat=3):
        if(B[i][j]>B[i][k]+B[k][j]):
            B[i][j]=B[i][k]+B[k][j]
            next[i][j]=next[i][k]
    Q=int(input())
    for _ in range(Q):
        s,t=map(int,input().split())
        s-=1; t-=1
        if(B[s][t]==INF):
            print(-1)
            continue
        # path restoration
        now=L
        count=0
        while(next[s][t]!=t):
            w=next[s][t]
            c=A[s][w]
            if(now<c):
                now=L-c
                count+=1
            else:
                now-=c
            s=w
        print(count+(now<A[s][t]))
resolve()

Submission status: Wrong Answer

Solution code:
from collections import deque
N,M,L = map(int,input().split())
load = [[]for i in range(N)]
for i in range(M):
    a,b,c = map(int,input().split())
    if c > L:
        continue
    load[a-1].append([b-1,c])
    load[b-1].append([a-1,c])
cost =[[float('inf')]*N for i in range(N)]
for i in range(N):
    queue = deque([i])
    cost[i][i] = 0
    while(queue):
        q = queue.popleft()
        gas = cost[i][q]
        for t,c in load[q]:
            if gas//L < (gas+c-1)//L :
                if (gas//L+1)*L+c < cost[i][t]:
                    cost[i][t] = (gas//L+1)*L+c
                    cost[t][i] = (gas//L+1)*L+c
                    queue.append(t)
            else:
                if gas+c < cost[i][t]:
                    cost[i][t] = gas+c
                    cost[t][i] = gas+c
                    queue.append(t)
Q = int(input())
for i in range(Q):
    s,t = map(int,input().split())
    ans = cost[s-1][t-1]
    if ans == float('inf'):
        print(-1)
    else:
        print((ans-1)//L)

Submission status: Wrong Answer

Solution code:
import heapq
n,m,l=map(int,input().split())
edge=[[] for i in range(n)]
for i in range(m):
  a,b,c=map(int,input().split())
  edge[a-1].append([c,b-1])
  edge[b-1].append([c,a-1])

def f(s):
  d=[float("inf")]*n
  used=[True]*n
  d[s]=0
  used[s]=False
  edgelist=[]
  ans=0
  cur=l
  for c,e in edge[s]:
    heapq.heappush(edgelist,(c,e))
  while edgelist:
    minedge=heapq.heappop(edgelist)
    v=minedge[1]
    ans,cur=minedge[0]//(10**10),minedge[0]%(10**10)
    used[v]=False
    d[v]=ans
    
    for e in edge[v]:
      if used[e[1]]:
        if e[0]>l:
          continue
        elif e[0]+cur>l:
          heapq.heappush(edgelist,((ans+1)*10**10+e[0],e[1]))
        else:
          heapq.heappush(edgelist,((ans)*10**10+e[0]+cur,e[1]))
  return d
Ans=[[] for i in range(n)]
for i in range(n):
  Ans[i]=f(i)
q=int(input())
for _ in range(q):
  s,t=map(int,input().split())
  print(-1 if Ans[s-1][t-1]==float("inf") else Ans[s-1][t-1])

Submission status: Wrong Answer

Solution code:
import heapq
n,m,l=map(int,input().split())
edge=[[] for i in range(n)]
for i in range(m):
  a,b,c=map(int,input().split())
  edge[a-1].append([c,b-1])
  edge[b-1].append([c,a-1])

def f(s):
  d=[float("inf")]*n
  used=[True]*n
  d[s]=0
  used[s]=False
  edgelist=[]
  ans=0
  cur=l
  for c,e in edge[s]:
    heapq.heappush(edgelist,(c,e))
  while edgelist:
    minedge=heapq.heappop(edgelist)
    v=minedge[1]
    ans,cur=minedge[0]//(10**10),minedge[0]%(10**10)
    used[v]=False
    d[v]=ans
    
    for e in edge[v]:
      if used[e[1]]:
        if e[0]>l:
          continue
        elif e[0]+cur>l:
          heapq.heappush(edgelist,((ans+1)*10**10+e[0],e[1]))
        else:
          heapq.heappush(edgelist,((ans)*10**10+e[0]+cur,e[1]))
  return d
Ans=[[] for i in range(n)]
for i in range(n):
  Ans[i]=f(i)
q=int(input())
for _ in range(q):
  s,t=map(int,input().split())
  print(Ans[s-1][t-1])

Submission status: Wrong Answer

Solution code:
import heapq
N,M,L=map(int,input().split())
G=[dict() for i in range(N)]
for i in range(M):
    a,b,t=map(int,input().split())
    if t<=L:
        G[a-1][b-1]=t
        G[b-1][a-1]=t
def dijkstra(adj, st):
    dist=[10**15 for i in range(N)]
    prev=[-1 for i in range(N)]
    dist[st]=0
    q=[]
    heapq.heappush(q,(0,st))
    while (len(q)!=0):
        prc,src=heapq.heappop(q)
        if dist[src]<prc:
            continue
        for dest in adj[src]:
            cost=adj[src][dest]
            if dist[dest]>dist[src]+cost:
                dist[dest]=dist[src]+cost
                heapq.heappush(q,(dist[dest],dest))
                prev[dest]=src
    return (dist,prev)
Ddd=[dijkstra(G,i) for i in range(N)]
DIST=[Ddd[i][0] for i in range(N)]
PREV=[Ddd[i][1] for i in range(N)]
def get_path(goal, prev):
    path = [goal]
    dest = goal
    while prev[dest] != -1:
        path.append(prev[dest])
        dest = prev[dest]
    return list(reversed(path))
Q=int(input())
for i in range(Q):
    s,t=map(int,input().split())
    s-=1;t-=1
    if DIST[s][t]==10**15:
        print(-1)
    else:
        PATH=get_path(t,PREV[s])
        M=len(PATH)
        #補給回数
        #dp1=[0 for q in range(M)]
        #最適なときの残り
        #dp2=[L for q in range(M)]
        #for q in range(M):
        nowpoint=L
        ans1=0
        for j in range(M-1):
            p=PATH[j]
            q=PATH[j+1]
            if nowpoint-G[p][q]<0:
                nowpoint=L
                ans1+=1
            nowpoint-=G[p][q]
        PATH=get_path(s,PREV[t])
        nowpoint=L
        ans2=0
        for j in range(M-1):
            p=PATH[j]
            q=PATH[j+1]
            if nowpoint-G[p][q]<0:
                nowpoint=L
                ans2+=1
            nowpoint-=G[p][q]
        print(min(ans1,ans2))

Submission status: Wrong Answer

Solution code:
n,m,l = map(int,input().split())
A = [list(map(int,input().split())) for i in range(m)]
q = int(input())
S = [list(map(int,input().split())) for i in range(q)]

for i in range(m):
    for j in range(2):
        A[i][j] -= 1
for i in range(q):
    for j in range(2):
        S[i][j] -= 1

# B = []
# for i in range(m):
#     if A[i][2] <= l:
#         B.append(A)

# print(S)

M = [[float("inf")] * n for i in range(n)]
for i in range(n):
    M[i][i] = 0
for i in range(m):
    # print(S[i])
    M[A[i][0]][A[i][1]] = A[i][2]
    M[A[i][1]][A[i][0]] = A[i][2]

H = [[0]*n for i in range(n)]
for i in range(n):
    for j in range(n):
        H[i][j] = M[i][j]

N = [[i for i in range(n)] for j in range(n)]

# print(N)

for k in range(n):
    for i in range(n):
        for j in range(n):
            if j != k and i != k and M[i][j] >= M[i][k]+M[k][j]:
                M[i][j] = M[i][k]+M[k][j]
                N[i][j] = N[i][k]

# print(N,M)
def e(i):
    a = S[i][0]
    b = S[i][1]
    c = l
    ans = 0
    end = 0
    while end == 0:
        # print(i,l)
        ne = N[a][b]
        if c < H[a][ne]:
            ans += 1
            c = l
        c -= H[a][ne]
        if c < 0:
            return -1
        if ne == b:
            end = 1
        a = ne
    return ans

for i in range(q):
    print(e(i))

Submission status: Wrong Answer

Solution code:
def Warshall_Floyd(edges,N):
    for k in range(N):
        for i in range(N):
            for j in range(i+1,N):
                if edges[i][j]>edges[i][k]+edges[k][j]:
                    edges[i][j]=edges[i][k]+edges[k][j]
                    if oil[i][k]<edges[k][j]:
                        oil[i][j]=l-edges[k][j]
                        time[i][j]=time[i][k]+1
                    else:
                        oil[i][j]=oil[i][k]-edges[k][j]
                        time[i][j]=time[i][k]


  #return edges


n,m,l=map(int,input().split())
inf=float('inf')
edges=[[inf]*n for i in range(n)]
oil=[[l]*n for i in range(n)]
time=[[0]*n for i in range(n)]
for i in range(m):
    a,b,c=map(int,input().split())
    if c>l:
        continue
    edges[a-1][b-1]=c
    edges[b-1][a-1]=c
    oil[a-1][b-1]=l-c
    oil[b-1][a-1]=l-c
Warshall_Floyd(edges,n)
q=int(input())
for i in range(q):
    s,t=map(int,input().split())
    if s>t:
        buf=s
        s=t
        t=buf
    print(time[s-1][t-1] if edges[s-1][t-1]!=inf else -1)

Submission status: Wrong Answer

Solution code:
from collections import deque
N,M,L = map(int,input().split())
load = [[]for i in range(N)]
for i in range(M):
    a,b,c = map(int,input().split())
    if c > L:
        continue
    load[a-1].append([b-1,c])
    load[b-1].append([a-1,c])
cost =[[float('inf')]*N for i in range(N)]
for i in range(N):
    queue = deque([i])
    cost[i][i] = 0
    while(queue):
        q = queue.popleft()
        gas = cost[i][q]
        for t,c in load[q]:
            if gas//L < (gas+c-1)//L :
                if (gas//L+1)*L+c < cost[i][t]:
                    cost[i][t] = (gas//L+1)*L+c
                    queue.append(t)
            else:
                if gas+c < cost[i][t]:
                    cost[i][t] = gas+c
                    queue.append(t)
Q = int(input())
for i in range(Q):
    s,t = map(int,input().split())
    print((cost[s-1][t-1]-1)//L)

Submission status: Wrong Answer

Solution code:
from itertools import product
def floyd_warshall(n, edge):

    rn = range(n)
    dist = [ [float('inf')] * n for i in rn]
    nxt  = [[0] * n for i in rn]
    
    for i in rn:
        dist[i][i] = 0
            
    for src, dest, distance in edge:
        dist[src-1][dest-1] = distance
        nxt[src-1][dest-1] = dest-1
    for k, i, j in product(rn, repeat=3):
        new_dist = dist[i][k] + dist[k][j]
        if new_dist < dist[i][j]:
            dist[i][j] = new_dist
            nxt[i][j]  = nxt[i][k]
    
    return dist, nxt

grafo = []
n,m,l = [int(i) for i in input().split()]

for i in range(m):
    a,b,c = [int(i) for i in input().split()]
    if c<=l:
        grafo.append([a,b,c])
        grafo.append([b,a,c])

dist, nxt = floyd_warshall(n, grafo)

q = int(input())
for i in range(q):
    s,t = [int(i) for i in input().split()]
    d = dist[s-1][t-1]
    path = [s-1]

    if d == float('inf'):
        print(-1)
        continue
        
    gas = l
    res = 0
    #print('------')
    #print(dist[t-1][s-1])
    while path[-1] != t-1:
        path.append(nxt[path[-1]][t-1])
        #print(gas, dist[path[-2]][path[-1]])
        if dist[path[-2]][path[-1]] > gas:
            gas = l
            res += 1
        
        gas -= dist[path[-2]][path[-1]]
        
    print(res)

Submission status: Wrong Answer

Solution code:
n,m,l = map(int,input().split())
inf = 10**18
dist = [[inf for i in range(n)] for j in range(n)]

for i in range(n):
    dist[i][i] = 0

for i in range(m):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    if c <= l:
        dist[a][b] = c
        dist[b][a] = c

next_point = [[j for j in range(n)] for i in range(n)]
for i in range(n):
    for j in range(n):
        for k in range(n):
            if dist[j][k] > dist[j][i] + dist[i][k]:
                next_point[j][k] = next_point[j][i]
                dist[j][k] = min(dist[j][k],dist[j][i] + dist[i][k])
q = int(input())
#print(dist)
#print(next_point)
for i in range(q):
    s,t = map(int,input().split())
    s -= 1
    t -= 1
    if dist[s][t] < inf:
        ans = 0
        now = l
        u = s
        while u != t:
            #print(now)
            next_u = next_point[u][t]
            if now < dist[u][next_u]:
                ans += 1
                now = l
            now -= dist[u][next_u]
            u = next_u
        print(ans)
    else:
        print(-1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import heapq
from itertools import accumulate
INF = float("inf")

# 無向グラフを仮定する。


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = [[] for _ in range(N)]

    def add_edge(self, s, t, w=1):
        self.E[s].append([t, w])
        self.E[t].append([s, w])


# def Warshall_Floyd(g: Graph):
#     N = g.N
#     dist = [[INF]*N for _ in range(N)]
#     for from_, toweights in enumerate(g.E):
#         for to_, w in toweights:
#             dist[from_][to_] = w

#     for k in range(N):
#         for i in range(N):
#             for j in range(N):
#                 dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
#     return dist


def shortestPath(g: Graph, s: int):
    dist = [INF]*g.N
    dist[s] = 0

    prev = [None]*g.N
    Q = []
    heapq.heappush(Q, (dist[s], s))

    while len(Q) > 0:
        _, u = heapq.heappop(Q)
        for v, w in g.E[u]:
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                prev[v] = u
                heapq.heappush(Q, (dist[v], v))
    return dist, prev


def solve(N: int,
          M: int,
          L: int,
          A: "List[int]",
          B: "List[int]",
          C: "List[int]",
          Q: int,
          s: "List[int]",
          t: "List[int]"):
    g = Graph(N)
    for i in range(M):
        if C[i] < L:
            g.add_edge(A[i]-1, B[i]-1, C[i])
    # dist = Warshall_Floyd(g)
    # print(*dist, sep="\n")

    for i in range(Q):
        dist, prev = shortestPath(g, s[i]-1)
        michi = []
        p = t[i]-1
        while p is not None:
            michi.append(p)
            p = prev[p]
        if len(michi) == 1:
            print(-1)
            continue
        a = [dist[m] for m in michi[::-1]]
        b = [a[j+1]-a[j] for j in range(len(a)-1)]
        # print(b)
        counter = 0
        tot = 0
        for aa in b:
            tot += aa
            if tot > L:
                counter += 1
                tot = aa
        print(counter)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    L = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    C = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    Q = int(next(tokens))  # type: int
    s = [int()] * (Q)  # type: "List[int]"
    t = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        s[i] = int(next(tokens))
        t[i] = int(next(tokens))
    solve(N, M, L, A, B, C, Q, s, t)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,m,l=map(int,input().split())
s=[[float("INF")for i in range(n)]for i in range(n)]
for i in range(m):
    a,b,c=map(int,input().split())
    s[a-1][b-1]=c
    s[b-1][a-1]=c
for i in range(n):
    for j in range(n):
        for h in range(n):
            s[i][j]=min(s[i][j],s[i][h]+s[h][j])
t=[[float("INF")for i in range(n)]for i in range(n)]
for i in range(n):
    for j in range(n):
        if s[i][j]<=l:
            t[i][j]=1
for i in range(n):
    for j in range(n):
        for h in range(n):
            t[i][j]=min(t[i][j],t[i][h]+t[h][j])
for i in range(int(input())):
    a,b=map(int,input().split())
    if t[a-1][b-1]!=float("INF"):
        print(t[a-1][b-1]-1)
    else:
        print(-1)

Submission status: Wrong Answer

Solution code:
import heapq
N,M,L=map(int,input().split())
G=[dict() for i in range(N)]
for i in range(M):
    a,b,t=map(int,input().split())
    if t<=L:
        G[a-1][b-1]=t
        G[b-1][a-1]=t
def dijkstra(adj, st):
    dist=[10**15 for i in range(N)]
    prev=[-1 for i in range(N)]
    dist[st]=0
    q=[]
    heapq.heappush(q,(0,st))
    while (len(q)!=0):
        prc,src=heapq.heappop(q)
        if dist[src]<prc:
            continue
        for dest in adj[src]:
            cost=adj[src][dest]
            if dist[dest]>dist[src]+cost:
                dist[dest]=dist[src]+cost
                heapq.heappush(q,(dist[dest],dest))
                prev[dest]=src
    return (dist,prev)
Ddd=[dijkstra(G,i) for i in range(N)]
DIST=[Ddd[i][0] for i in range(N)]
PREV=[Ddd[i][1] for i in range(N)]
def get_path(goal, prev):
    path = [goal]
    dest = goal
    while prev[dest] != -1:
        path.append(prev[dest])
        dest = prev[dest]
    return list(reversed(path))
Q=int(input())
for i in range(Q):
    s,t=map(int,input().split())
    s-=1;t-=1
    if DIST[s][t]==10**15:
        print(-1)
    else:
        PATH=get_path(t,PREV[s])
        M=len(PATH)
        nowpoint=L
        ans=0
        for j in range(M-1):
            p=PATH[j]
            q=PATH[j+1]
            if nowpoint-G[p][q]<=0:
                nowpoint=L
                ans+=1
            nowpoint-=G[p][q]
        print(ans)

Submission status: Wrong Answer

Solution code:
N, M, L = list(map(int, input().split()))
ABC = [list(map(int, input().split())) for _ in range(M)]
Q = int(input())
st = [list(map(int, input().split())) for _ in range(Q)]

D = [[0] * N for _ in range(N)]
R = {}

for a, b, c in ABC:
  a -= 1
  b -= 1
  D[a][b] = c
  D[b][a] = c
  if a not in R:
    R[a] = [[b, c]]
  else:
    R[a].append([b, c])
  if b not in R:
    R[b] = [[a, c]]
  else:
    R[b].append([a, c])

inf = 10 ** 10
T = [[inf] * N for _ in range(N)]
import copy
for i in range(N):
  if i not in R: continue
  S = copy.deepcopy(R[i])
  T[i][i] = 0
  while S:
    t = S.pop()
    if t[1] <= L:
      if t[1] < T[i][t[0]]:
        T[i][t[0]] = t[1]
        for j in R[t[0]]:
          if t[1] + j[1] <= L:
            S.append([j[0], t[1] + j[1]])

for i in range(N):
  for j in range(N):
    if T[i][j] <= L:
      T[i][j] = 1
    else:
      T[i][j] = inf

for i in range(N):
  for j in range(N):
    for k in range(N):
      T[i][j] = min(T[i][j], T[i][k] + T[k][j])

for s, t in st:
  s -= 1
  t -= 1
  if T[s][t] == inf:
    print(-1)
  else:
    print(T[s][t] - 1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from itertools import product

INF = float('inf')
def floyd_warshall(V, E):
    '''
    Input:
        V = list(range(N))
        E = defaultdict(dict)
    Output:
        If there exists a negative cycle, return (None, prev), where prev is
        the table, whose (i, j)-element is the previous vertices in the shortest (i, j)-path
        Otherwise return (dist, prev), where dist is the table of the minimum cost
        between arbitrary vertex u, v in the given graph
    '''
    N = len(V)
    dist = {u: {v: INF for v in V} for u in V}
    prev = {u: {v: None for v in V} for u in V}
    for v in V:
        dist[v][v] = 0; prev[v][v] = -1
        for u, c in E[v].items(): dist[v][u] = c; prev[v][u] = v;
    for k in V:        
        for i, j in product(V, repeat=2):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
                prev[i][j] = prev[k][j]
    for v in V:
        if dist[v][v] < 0: return None, prev
    return dist, prev

def path_reconstruction(V, prev, u, v):
    P = [v]
    prev_u = prev[u]
    while prev_u[v] != -1:
        v = prev_u[v]
        P.append(v)
        if v == P[0]: break
    return list(reversed(P))

N, M, L = map(int, input().split())
V = list(range(N))
E = defaultdict(dict)
for _ in range(M):
    a, b, c = map(int, input().split())
    E[a-1][b-1] = c
    E[b-1][a-1] = c

dist, prev = floyd_warshall(V, E)

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    if dist[s-1][t-1] == INF: print(-1)
    else:
        ans = 0
        fuel = L
        path = path_reconstruction(V, prev, s-1, t-1)
        for p1, p2 in zip(path, path[1:]):
            dis = E[p1][p2]
            if L < dis:
                ans = -1; break
            elif fuel < dis:
                fuel = L; ans += 1
            fuel -= dis
        print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
N,M,L=map(int,input().split())
G=[dict() for i in range(N)]
for i in range(M):
    a,b,t=map(int,input().split())
    if t<=L:
        G[a-1][b-1]=t
        G[b-1][a-1]=t
def dijkstra(adj, st):
    dist=[10**15 for i in range(N)]
    prev=[-1 for i in range(N)]
    dist[st]=0
    q=[]
    heapq.heappush(q,(0,st))
    while (len(q)!=0):
        prc,src=heapq.heappop(q)
        if dist[src]<prc:
            continue
        for dest in adj[src]:
            cost=adj[src][dest]
            if dist[dest]>dist[src]+cost:
                dist[dest]=dist[src]+cost
                heapq.heappush(q,(dist[dest],dest))
                prev[dest]=src
    return (dist,prev)
Ddd=[dijkstra(G,i) for i in range(N)]
DIST=[Ddd[i][0] for i in range(N)]
PREV=[Ddd[i][1] for i in range(N)]
def get_path(goal, prev):
    path = [goal]
    dest = goal
    while prev[dest] != -1:
        path.append(prev[dest])
        dest = prev[dest]
    return list(reversed(path))
Q=int(input())
for i in range(Q):
    s,t=map(int,input().split())
    s-=1;t-=1
    if DIST[s][t]==10**15:
        print(-1)
    else:
        PATH=get_path(t,PREV[s])
        M=len(PATH)
        nowpoint=L
        ans=0
        for j in range(M-1):
            p=PATH[j]
            q=PATH[j+1]
            if nowpoint-G[p][q]<0:
                nowpoint=L
                ans+=1
            nowpoint-=G[p][q]
        print(ans)

Submission status: Wrong Answer

Solution code:
inf = 10**10
from collections import deque
def warshall_floyd(d):#d[u][v]:辺uvのコスト.存在しなければinf.d[i][i]は0
    for i in range(N):#0~iとa, bのみを使う最短経路を考える
        for a in range(N):
            for b in range(N):
                d[a][b] = min(d[a][b], d[a][i]+ d[i][b])#頂点iを使う場合と使わない場合
    return d
N, M, L = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    G[a-1].append((b-1, c))
    G[b-1].append((a-1, c))
G2 = [[-1]*N for _ in range(N)]
for v0 in range(N):
    G2[v0][v0] = L
    que = deque([v0])
    while que:
        v = que.pop()
        l = G2[v0][v]
        for nv, c in G[v]:
            if G2[v0][nv] >0 or l-c<0:
                continue
            G2[v0][nv] = l-c
            que.append(nv)
for i in range(N):
    for j in range(N):
        if i == j:
            G2[i][j] = 0
        elif G2[i][j]>=0:
            G2[i][j] = 1
        else:
            G2[i][j] = inf
d = warshall_floyd(G2)
Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    ans = d[s-1][t-1]-1
    print(ans if ans < 10**9 else -1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N,M,L=map(int,input().split())

E=[[] for i in range(N+1)]

for i in range(M):
    a,b,cost=map(int,input().split())

    E[a].append((b,cost))
    E[b].append((a,cost))


Q=int(input())
Query=[list(map(int,input().split())) for i in range(Q)]

ANS=[[(N+10,0) for i in range(N+1)] for j in range(N+1)]

from collections import deque

for start in range(1,N+1):

    ANS[start][start]=(0,0)
    USE=[0]*(N+1)

    QUE=deque()

    QUE.append(start)

    while QUE:
        x=QUE.pop()
        USE[x]=1
        h,cost0=ANS[start][x]

        for to,cost in E[x]:
            if USE[to]==1:
                continue
            
            if cost0+cost<=L and (h,cost0+cost)<ANS[start][to]:
                ANS[start][to]=(h,cost0+cost)
                QUE.append(to)

            elif cost<=L and (h+1,cost)<ANS[start][to]:
                ANS[start][to]=(h+1,cost)
                QUE.append(to)

for x,y in Query:
    if ANS[x][y][0]==N+10:
        print(-1)
    else:
        print(ANS[x][y][0])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N,M,L=map(int,input().split())

E=[[] for i in range(N+1)]

for i in range(M):
    a,b,cost=map(int,input().split())

    E[a].append((b,cost))
    E[b].append((a,cost))


Q=int(input())
Query=[list(map(int,input().split())) for i in range(Q)]

ANS=[[(N+10,0) for i in range(N+1)] for j in range(N+1)]

from collections import deque

for start in range(1,N+1):

    ANS[start][start]=(0,0)
    USE=[0]*(N+1)

    QUE=deque()

    QUE.append(start)

    while QUE:
        x=QUE.pop()
        USE[x]=1
        h,cost0=ANS[start][x]

        for to,cost in E[x]:
            if USE[to]==1:
                continue
            
            if cost0+cost<=L and (h,cost0+cost)<ANS[start][to]:
                ANS[start][to]=(h,cost0+cost)
                QUE.append(to)

            elif (h+1,cost)<ANS[start][to]:
                ANS[start][to]=(h+1,cost)
                QUE.append(to)

for x,y in Query:
    if ANS[x][y][0]==N+10:
        print(-1)
    else:
        print(ANS[x][y][0])

Submission status: Wrong Answer

Solution code:
n,m,L=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
q=int(input())
ql=[list(map(int,input().split())) for i in range(q)]
distance=[[10**17]*n for i in range(n)]
for i in range(m):
  if l[i][2]<=L:
    distance[l[i][0]-1][l[i][1]-1]=l[i][2]
    distance[l[i][1]-1][l[i][0]-1]=l[i][2]
for i in range(n):
  for j in range(n):
    for k in range(n):
      distance[j][k]=min(distance[j][k],distance[j][i]+distance[i][k])

for i in range(q):
  if distance[ql[i][0]-1][ql[i][1]-1]<=10*18:
    print(distance[ql[i][0]-1][ql[i][1]-1]//L)
  else:
    print(-1)