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 heapq import *
N,M,L=map(int,input().split())
costable=[[float("inf") for _ in range(N)] for _ in range(N)]
needoil=[[float("inf") for _ in range(N)] for _ in range(N)]
needing=0
tree=[[] for _ in range(N)]
for i in range(M):
    a,b,c=map(int,input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
    costable[a-1][b-1]=c
    costable[b-1][a-1]=c
Q=int(input())
query=[list(map(int,input().split())) for _ in range(Q)]
for i in range(N):
    q=[]
    q.append([0,i,L])
    needoil[i][i]=0
    heapify(q)
    #print(q)
    while len(q)>0:
        needingnum,u,nowoil=heappop(q)
        #print(needingnum,u,nowoil)
        if needoil[i][u]<needingnum:continue
        #if nowoil!=L:
        #    q.heappush([needingnum+1,i,L])
        for j in tree[u]:
            nextoil=nowoil-costable[u][j]
            nextoilwithcharge=L-costable[u][j]
            if (nextoil>=0)and(needingnum<needoil[i][j]):
                needoil[i][j]=needingnum
                heappush(q,[needingnum,j,nextoil])
                #heappush(q, [needingnum+1, j, nextoilwithcharge])
            elif (nextoilwithcharge>=0)and(needingnum+1<needoil[i][j]):
                needoil[i][j] = needingnum+1
                heappush(q,[needingnum+1,j,nextoilwithcharge])
        #print(needoil,q)
        #input()
for l in query:
    u,v=l
    num=needoil[u-1][v-1]
    if num==float("inf"):
        print(-1)
    else:
        print(num)

Submission status: Wrong Answer

Solution code:
from heapq import *
N,M,L=map(int,input().split())
costable=[[float("inf") for _ in range(N)] for _ in range(N)]
needoil=[[float("inf") for _ in range(N)] for _ in range(N)]
needing=0
tree=[[] for _ in range(N)]
for i in range(M):
    a,b,c=map(int,input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
    costable[a-1][b-1]=c
    costable[b-1][a-1]=c
Q=int(input())
query=[list(map(int,input().split())) for _ in range(Q)]
for i in range(N):
    q=[]
    q.append([0,i,L])
    needoil[i][i]=0
    heapify(q)
    #print(q)
    while len(q)>0:
        needingnum,u,nowoil=heappop(q)
        #print(needingnum,u,nowoil)
        if needoil[i][u]<needingnum:continue
        #if nowoil!=L:
        #    q.heappush([needingnum+1,i,L])
        for j in tree[u]:
            nextoil=nowoil-costable[u][j]
            nextoilwithcharge=L-costable[u][j]
            if (nextoil>=0)and(needingnum<needoil[i][j]):
                needoil[i][j]=needingnum
                heappush(q,[needingnum,j,nextoil])
                heappush(q, [needingnum+1, j, nextoilwithcharge])
            elif (nextoilwithcharge>=0)and(needingnum+1<needoil[i][j]):
                needoil[i][j] = needingnum+1
                heappush(q,[needingnum+1,j,nextoilwithcharge])
        #print(needoil,q)
        #input()
for l in query:
    u,v=l
    num=needoil[u-1][v-1]
    if num==float("inf"):
        print(-1)
    else:
        print(num)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# E

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect

# 再起回数上限変更
# sys.setrecursionlimit(1000000)


class Dijkstra(object):
    """ ある特定の点からそのほかの頂点への最小距離を求める
    最短区間を実現するルートについては、prevに格納していく
    """
    def __init__(self, n:int):
        self.adjacency_dict = {}
        self.n = n
        for i in range(n):
            self.add_vertex(i)

    def add_vertex(self, v: int):
        """ ノードを追加する """
        self.adjacency_dict[v] = {}

    def add_edge(self, v1: int, v2: int, w: float, undirected=False):
        self.adjacency_dict[v1][v2] = w
        if undirected:
            self.adjacency_dict[v2][v1] = w

    def run(self, start: int) -> (list, list):
        """ startから初めてそれ以外のノードへの最短距離をダイクストラ法で求める """
        # sからの距離とその前のノードを管理する
        dist = [float('inf')] * self.n
        prev = [None] * self.n
        heap_q = []

        dist[start] = 0

        # プライオリティキューでstartから各ノードの(最短距離, ノードindex)を管理する
        heappush(heap_q, (0, start))

        while len(heap_q) > 0:
            # 未確定な中から最小のノードを取得し、確定する
            d, l = heappop(heap_q)

            # 最小のノードから直接リンクしているノードについて、距離が縮まるようであれば更新する
            for node in self.adjacency_dict[l].keys():
                new_dist = dist[l] + self.adjacency_dict[l][node]
                if dist[node] > new_dist:
                    dist[node] = new_dist
                    heappush(heap_q, (new_dist, node))
                    prev[node] = l

        return dist, prev


if __name__ == '__main__':
    N, M, L = map(int, input().split())

    g = Dijkstra(N)
    for _ in range(M):
        v1, v2, w = map(int, input().split())
        if w <= L:
            g.add_edge(v1 - 1, v2 - 1, w, undirected=True)

    # print(g.adjacency_dict)

    res = {}
    route = {}
    for i in range(N):
        dist, prev = g.run(start=i)
        res[i] = dist
        route[i] = prev

    Q = int(input())
    for _ in range(Q):
        s, t = map(int, input().split())
        s, t = s-1, t-1
        val = res[s][t]
        if val == float('inf'):
            print(-1)
        else:
            tmp = t
            ord = []

            while True:
                tmp = route[s][tmp]
                ord.append(tmp)
                if tmp == s:
                    break
            # print((s, t), ord)
            ord = ord[::-1] + [t]
            ans = 0
            dist = L
            for i in range(len(ord)-1):
                val = g.adjacency_dict[ord[i]][ord[i+1]]
                # print(val)
                if dist - val < 0:
                    ans += 1
                    dist = L - val
                else:
                    dist -= val

            print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import *
INF = 1e10
respostas = []

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

d = [ [INF] * N for i in range(N)]

for x in range(M):
    a,b,w = map(int,input().split())
    d[a-1][b-1] = w
    d[b-1][a-1] = w
    d[a-1][a-1] = 0
    d[b-1][b-1] = 0

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

grafo2 = d

for x in range(len(grafo2)):
    for y in range(len(grafo2[x])) :
        if grafo2[x][y] < L:
            grafo2[x][y] = 1
            grafo2[y][x] = 1
        elif x == y:
            grafo2[x][y] = 0
            grafo2[y][x] = 0

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

query = int(input())

for x in range(query):
    s,t = map(int,input().split())
    if grafo2[s-1][t-1] == INF:
        respostas.append(-1)
    else:
        respostas.append(grafo2[s-1][t-1] - 1)

for x in respostas:
    print(x)

Submission status: Wrong Answer

Solution code:
from heapq import *
INF = 1e10
respostas = []

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

d = [ [INF] * N for i in range(N)]

for x in range(M):
    a,b,w = map(int,input().split())
    d[a-1][b-1] = w
    d[b-1][a-1] = w
    d[a-1][a-1] = 0
    d[b-1][b-1] = 0

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

grafo2 = d

for x in range(len(grafo2)):
    for y in range(len(grafo2[x])) :
        if grafo2[x][y] <= L:
            grafo2[x][y] = 1
            grafo2[y][x] = 1

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

query = int(input())

for x in range(query):
    s,t = map(int,input().split())
    if grafo2[s-1][t-1] == INF:
        respostas.append(-1)
    else:
        respostas.append(grafo2[s-1][t-1] - 1)

for x in respostas:
    print(x)

Submission status: Wrong Answer

Solution code:
import sys

def main():
  input = sys.stdin.readline
  n, m, l = map(int, input().split())

  inf = pow(10, 20)
  towns_c = [[inf]*n for _ in range(n)]
  towns_s = [[inf]*n for _ in range(n)]
  towns_g = [[inf]*n for _ in range(n)]
  
  for _ in range(m):
    a, b, c = map(int, input().split())
    if c > l:
      continue
    towns_c[a-1][b-1] = 0
    towns_c[b-1][a-1] = 0
    towns_s[a-1][b-1] = c
    towns_s[b-1][a-1] = c
    towns_g[a-1][b-1] = c
    towns_g[b-1][a-1] = c
  
  for k in range(n):
    for i in range(n):
      for j in range(n):
        key = towns_c[i][k]+towns_c[k][j]
        key_plus = 0
        if towns_g[i][k]+towns_s[k][j] > l:
          key_plus = 1
        if towns_c[i][j] > key+key_plus:
          towns_c[i][j] = key+key_plus
          s, g = towns_s[i][k], towns_g[k][j]
          if towns_c[i][k] == 0 and key_plus == 0:
            s += towns_s[k][j]
          if towns_c[k][j] == 0 and key_plus == 0:
            g += towns_g[i][k]
          towns_s[i][j] = s
          towns_g[i][j] = g
  
  q = int(input())
  for _ in range(q):
    s, t = map(int, input().split())
    if towns_c[s-1][t-1] == inf:
      print(-1)
    else:
      print(towns_c[s-1][t-1])

if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

sys.setrecursionlimit(10 ** 7)

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

def floyd_warshall(n, dist):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k])


n, m, l = na()
abc = nan(m)
q = ni()
st = nan(q)

g = [[] for _ in range(n)]
dist = [[inf] * n for _ in range(n)]
for i in range(m):
    a, b, c = abc[i]
    a -= 1
    b -= 1
    dist[a][b] = c
    dist[b][a] = c

floyd_warshall(n, dist)

ans = [[inf] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if dist[i][j] <= l:
            ans[i][j] = 1
            ans[j][i] = 1

floyd_warshall(n, ans)

for i in range(q):
    s, t = st[i]
    s -= 1
    t -= 1
    if dist[s][t] >= inf:
        print(-1)
    else:
        print(ans[s][t] - 1)

Submission status: Wrong Answer

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

n, m, l = 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)]

graph = [[] for _ in range(n)]
for a, b, c in abc:
    graph[a-1].append([c, b-1])
    graph[b-1].append([c, a-1])

for s, t in st:
    state = [[10**5, -1] for _ in range(n)]
    state[s-1] = [0, l]
    que = [[0, s-1]]
    heapq.heapify(que)
    while que:
        x, y = heapq.heappop(que)
        if y == t-1:
            print(state[y][0])
            break
        for i, j in graph[y]:
            if (state[y][1] - i >= 0 and state[j][0] > state[y][0]) or (state[y][1] - i >= 0 and state[j][0] == state[y][0] and state[j][1] <= state[y][1] - i):
                state[j] = [state[y][0], state[y][1] - i]
                heapq.heappush(que, [i, j])
                continue
            if (state[y][1] - i < 0 and l - i >= 0 and state[j][0] > state[y][0] + 1) or (state[y][1] - i < 0 and l - i >= 0 and state[j][0] == state[y][0] + 1 and state[j][1] <= l - i):
                state[j] = [state[y][0] + 1, l - i]
                heapq.heappush(que, [i, j])
    if y != t-1:
        print(-1)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    inf = 10**17
    #mod = 10**9 + 7

    n,m,l = map(int, input().split())
    edge = [[] for i in range(n)]
    #edge[i] : iから出る道の[重み,行先]の配列
    for _ in range(m):
        x,y,z = map(int,input().split())
        edge[x-1].append((z,y-1))
        edge[y-1].append((z,x-1))

    def dfs(start):
        d = [inf]*n
        d[start] = 0
        f = [-1]*n
        f[start] = l
        dq = deque([[start, l]])
        while dq:
            v, nl = dq.pop()
            for c, nv in edge[v]:
                if l - c < 0:
                    continue
                if nl - c >= 0:
                    if d[v] < d[nv] or (d[v]==d[nv]and f[nv] < nl - c):
                        f[nv] = nl - c
                        d[nv] = d[v]
                        dq.append([nv, nl-c])
                else:
                    if d[v]+1 < d[nv] or (d[v]+1==d[nv] and f[nv] < l-c):
                        f[nv] = l - c
                        d[nv] = d[v] + 1
                        dq.append([nv, l-c])
        return d

    res = []
    for i in range(n):
        res.append(dfs(i))

    q = int(input())
    ans = []
    for _ in range(q):
        s,t = map(int, input().split())
        if res[s-1][t-1] == inf:
            ans.append(-1)
        else:
            ans.append(res[s-1][t-1])
    
    for i in ans:
        print(i)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    inf = 10**17
    #mod = 10**9 + 7

    n,m,l = map(int, input().split())
    edge = [[] for i in range(n)]
    #edge[i] : iから出る道の[重み,行先]の配列
    for _ in range(m):
        x,y,z = map(int,input().split())
        edge[x-1].append((z,y-1))
        edge[y-1].append((z,x-1))

    def bfs(start):
        d = [inf]*n
        d[start] = 0
        f = [-1]*n
        f[start] = l
        dq = deque([[start, l]])
        while dq:
            v, nl = dq.popleft()
            for c, nv in edge[v]:
                if l - c < 0:
                    continue
                if nl - c >= 0:
                    if d[v] < d[nv] or (d[v]==d[nv]and f[nv] < nl - c):
                        f[nv] = nl - c
                        d[nv] = d[v]
                        dq.append([nv, nl-c])
                else:
                    if d[v]+1 < d[nv] or (d[v]+1==d[nv] and f[nv] < l-c):
                        f[nv] = l - c
                        d[nv] = d[v] + 1
                        dq.append([nv, l-c])
        return d

    res = []
    for i in range(n):
        res.append(bfs(i))

    q = int(input())
    ans = []
    for _ in range(q):
        s,t = map(int, input().split())
        if res[s-1][t-1] == inf:
            ans.append(-1)
        else:
            ans.append(res[s-1][t-1])
    
    for i in ans:
        print(i)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    inf = 10**17
    #mod = 10**9 + 7

    n,m,l = map(int, input().split())
    edge = [[] for i in range(n)]
    #edge[i] : iから出る道の[重み,行先]の配列
    for _ in range(m):
        x,y,z = map(int,input().split())
        edge[x-1].append((z,y-1))
        edge[y-1].append((z,x-1))

    def bfs(start):
        d = [inf]*n
        d[start] = 0
        f = [0]*n
        f[start] = l
        dq = deque([[start, l]])
        while dq:
            v, nl = dq.popleft()
            for c, nv in edge[v]:
                if l - c < 0:
                    continue
                if nl - c >= 0:
                    if d[v] < d[nv] or (d[v]==d[nv]and f[nv] < nl - c):
                        f[nv] = nl - c
                        d[nv] = d[v]
                        dq.append([nv, nl-c])
                else:
                    if d[v]+1 < d[nv] or (d[v]+1==d[nv] and f[nv] < l-c):
                        f[nv] = l - c
                        d[nv] = d[v] + 1
                        dq.append([nv, l-c])
        return d

    res = []
    for i in range(n):
        res.append(bfs(i))

    q = int(input())
    ans = []
    for _ in range(q):
        s,t = map(int, input().split())
        if res[s-1][t-1] == inf:
            ans.append(-1)
        else:
            ans.append(res[s-1][t-1])
    
    for i in ans:
        print(i)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    inf = 10**17
    #mod = 10**9 + 7

    n,m,l = map(int, input().split())
    edge = [[] for i in range(n)]
    #edge[i] : iから出る道の[重み,行先]の配列
    for _ in range(m):
        x,y,z = map(int,input().split())
        edge[x-1].append((z,y-1))
        edge[y-1].append((z,x-1))

    def bfs(start):
        d = [inf]*n
        d[start] = 0
        f = [inf]*n
        f[start] = l
        dq = deque([[start, l]])
        while dq:
            v, nl = dq.popleft()
            for c, nv in edge[v]:
                if l - c < 0:
                    continue
                if nl - c >= 0:
                    if d[v] < d[nv] or (d[v]==d[nv]and f[nv] < nl - c):
                        f[nv] = nl - c
                        d[nv] = d[v]
                        dq.append([nv, nl-c])
                else:
                    if d[v]+1 < d[nv] or (d[v]+1==d[nv] and f[nv] < l-c):
                        f[nv] = l - c
                        d[nv] = d[v] + 1
                        dq.append([nv, l-c])
        return d

    res = []
    for i in range(n):
        res.append(bfs(i))

    q = int(input())
    ans = []
    for _ in range(q):
        s,t = map(int, input().split())
        if res[s-1][t-1] == inf:
            ans.append(-1)
        else:
            ans.append(res[s-1][t-1])
    
    for i in ans:
        print(i)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    inf = 10**17
    #mod = 10**9 + 7

    n,m,l = map(int, input().split())
    edge = [[] for i in range(n)]
    #edge[i] : iから出る道の[重み,行先]の配列
    for _ in range(m):
        x,y,z = map(int,input().split())
        edge[x-1].append((z,y-1))
        edge[y-1].append((z,x-1))

    def bfs(start):
        d = [inf]*n
        d[start] = 0
        f = [inf]*n
        f[start] = l
        dq = deque([[start, l]])
        while dq:
            v, nl = dq.popleft()
            for c, nv in edge[v]:
                if l - c < 0:
                    continue
                if nl - c >= 0:
                    if f[nv] > nl - c:
                        f[nv] = nl - c
                        d[nv] = min(d[nv], d[v])
                        dq.append([nv, nl-c])
                else:
                    if d[v] + 1 <= d[nv] and f[nv] > l-c:
                        f[nv] = l - c
                        d[nv] = d[v] + 1
                        dq.append([nv, l-c])
        return d

    res = []
    for i in range(n):
        res.append(bfs(i))

    q = int(input())
    ans = []
    for _ in range(q):
        s,t = map(int, input().split())
        #-1
        if res[s-1][t-1] == inf:
            ans.append(-1)
        else:
            ans.append(res[s-1][t-1])
    
    for i in ans:
        print(i)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, M, L = map(int, input().split())
import heapq

query = [[-1]*N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    query[a-1][b-1] = c
    query[b-1][a-1] = c

def dijkstra(N, L, s, g):
    checked = [0]*N
    queue = []
    heapq.heappush(queue, ((0, L), s))
    dp = [-1]*N

    while queue:
        (t, e), v = heapq.heappop(queue)
        if checked[v]:
            continue
        checked[v] = 1
        dp[v] = (t, e)
        if v==g:
            return dp[v][0]
        for i in range(N):
            tt = t
            te = e
            if checked[i]==0 and query[v][i]!=-1:
                dist = query[v][i]
                if dist>e:
                    tt += 1
                    te = L+e-dist
                else:
                    te -= dist
                heapq.heappush(queue, ((tt, te), i))
    return -1

Q = int(input())
for _ in range(Q):
    a, b = map(int, input().split())
    print(dijkstra(N, L, a-1, b-1))

Submission status: Wrong Answer

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

INF = 10 ** 9
lst1 = [[INF] * (N + 1) for _ in range(N+1)] #頂点1に隣接する辺以外の道の管理
# u-->vへコストlで行ける時
for i in range(N+1):
    lst1[i][i] = 0
for _ in range(M):
    a, b, c = map(int, input().split())
    lst1[a][b] = c
    lst1[b][a] = c

# 処理する部分
def WarshallFloyd(lst):
    for k in range(N+1):
        for i in range(N+1):
            for j in range(N+1):
                lst[i][j] = min(lst[i][j], lst[i][k] + lst[k][j])
    return
# i-->jのコストはlst[i][j]

WarshallFloyd(lst1)

lst2 = [[INF] * (N + 1) for _ in range(N + 1)]
for i in range(N):
    lst2[i][i] = 0
    for j in range(i + 1, N + 1):
        if lst1[i][j] <= L:
            lst2[i][j] = 1
            lst2[j][i] = 1

WarshallFloyd(lst2)

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    if lst2[s][t] >= INF:
        print (-1)
    else:
        print (max(lst2[s][t] - 1, 0))

Submission status: Wrong Answer

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

INF = 10 ** 9
lst1 = [[INF] * (N + 1) for _ in range(N+1)] #頂点1に隣接する辺以外の道の管理
# u-->vへコストlで行ける時
for i in range(N+1):
    lst1[i][i] = 0
for _ in range(M):
    a, b, c = map(int, input().split())
    lst1[a][b] = c
    lst1[b][a] = c

# 処理する部分
def WarshallFloyd(lst):
    for k in range(N+1):
        for i in range(N+1):
            for j in range(N+1):
                lst[i][j] = min(lst[i][j], lst[i][k] + lst[k][j])
    return
# i-->jのコストはlst[i][j]

WarshallFloyd(lst1)

lst2 = [[INF] * (N + 1) for _ in range(N + 1)]
for i in range(N):
    lst2[i][i] = 0
    for j in range(i + 1, N + 1):
        if lst1[i][j] <= L:
            lst2[i][j] = 1
            lst2[j][i] = 1

WarshallFloyd(lst2)

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    if lst2[s][t] >= INF:
        print (-1)
    else:
        print (lst2[s][t] - 1)

Submission status: Wrong Answer

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

INF = 10 ** 9
lst1 = [[INF] * (N + 1) for _ in range(N+1)] #頂点1に隣接する辺以外の道の管理
# u-->vへコストlで行ける時
for i in range(N+1):
    lst1[i][i] = 0
for _ in range(M):
    a, b, c = map(int, input().split())
    lst1[a][b] = c
    lst1[b][a] = c

# 処理する部分
def WarshallFloyd(lst):
    for k in range(N+1):
        for i in range(N+1):
            for j in range(N+1):
                lst[i][j] = min(lst[i][j], lst[i][k] + lst[k][j])
    return
# i-->jのコストはlst[i][j]

WarshallFloyd(lst1)

lst2 = [[INF] * (N + 1) for _ in range(N + 1)]
for i in range(N):
    lst2[i][i] = 0
    for j in range(i + 1, N + 1):
        if lst1[i][j] <= L:
            lst2[i][j] = 1
            lst2[j][i] = 1

WarshallFloyd(lst2)

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    if lst2[s][t] == INF:
        print (-1)
    else:
        print (lst2[s][t] - 1)

Submission status: Wrong Answer

Solution code:
INFTY = 10**12
N,M,L = map(int,input().split())
G = {i:[] for i in range(1,N+1)}
for _ in range(M):
    a,b,c = map(int,input().split())
    G[a].append((b,c))
    G[b].append((a,c))
dist = [[INFTY for _ in range(N+1)] for _ in range(N+1)]
for i in range(1,N+1):
    for j,d in G[i]:
        dist[i][j] = d
for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j])
F = {i:[] for i in range(1,N+1)}
for i in range(1,N+1):
    for j in range(1,N+1):
        if dist[i][j]<=L:
            F[i].append(j)
dist2 = [[INFTY for _ in range(N+1)] for _ in range(N+1)]
for i in range(1,N+1):
    for j in F[i]:
        dist2[i][j] = 1
for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            dist2[i][j] = min(dist2[i][j],dist2[i][k]+dist2[k][j])
Q = int(input())
for _ in range(Q):
    s,t = map(int,input().split())
    if dist2[s][t]>=INFTY:
        print(-1)
    else:
        print(dist2[s][t])

Submission status: Wrong Answer

Solution code:
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 _ in range(N)]
for a,b,c in ABC:
    a,b = a-1,b-1
    es[a].append((b,c))
    es[b].append((a,c))

B = 10**10
INF = 9999*B
import heapq
ds = [[INF]*N for _ in range(N)]
for i in range(N):
    ds[i][i] = 0

for i in range(N):
    hq = [(0,i)]
    heapq.heapify(hq)
    while hq:
        c,v = heapq.heappop(hq)
        d,m = divmod(c,B)
        for to,co in es[v]:
            if m+co <= L:
                nc = d*B + m+co
            else:
                nc = (d+1)*B + co
            if nc >= ds[i][to]: continue
            ds[i][to] = nc
            heapq.heappush(hq, (nc,to))

ans = []
for s,t in ST:
    s,t = s-1,t-1
    if ds[s][t] == INF:
        ans.append(-1)
    else:
        ans.append(ds[s][t]//B)
print(*ans, sep='\n')

Submission status: Wrong Answer

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

from collections import deque
Q=int(input())
for i in range(Q):
  s,t=map(int,input().split())
  s-=1
  t-=1
  if m==0:
    print(-1)
    exit(0)
  fuel=[-1]*n
  fuel[s]=l
  cnt=[0]*n
  cnt[s]=0
  q=deque()
  q.append(s)
  ok=True
  while q:
    cur=q.popleft()
    for nx,nx_dist in G[cur]:
      if fuel[t]!=-1:break
      if fuel[nx]==-1:
        if l-nx_dist>=0:
          if fuel[cur]-nx_dist>=0:
            fuel[nx]=fuel[cur]-nx_dist
            cnt[nx]=cnt[cur]
          else:
            cnt[nx]=cnt[cur]+1
            fuel[cur]=l
            fuel[nx]=fuel[cur]-nx_dist  
          q.append(nx)
        else:
          continue
  print(cnt[t])

Submission status: Wrong Answer

Solution code:

n,m,l=map(int,input().split())

#基本的にワーシャルフロイドの場合、行列式のリストで距離を保管する
from scipy.sparse import csr_matrix
from scipy.sparse import csgraph 

d = [[10**12 for i in range(n+1)] for i in range(n+1)]

for i in range(m):
    x,y,z = map(int,input().split())
    #有向グラフか無向グラフかによってここで場合わけが生じる
    d[x][y] = z
    d[y][x] = z
    
for i in range(n+1):
    d[i][i] = 0 #自身のところに行くコストは０
q=int(input())
que=[]
for _ in range(q):
    s,t=map(int,input().split())
    que.append((s,t))
       
csr=csr_matrix(d)
K=csgraph.shortest_path(csr,method="FW",directed=True)
e = [[10**12 for i in range(n+1)] for i in range(n+1)]

for i in range(1,n+1):
    for j in range(1,n+1):
        if K[i][j]<=l:
            e[i][j]=1
            
for i in range(n+1):
    e[i][i]=0
    

A=csr_matrix(e)
ANS=csgraph.shortest_path(A,method="FW",directed=True)

for some in que:
    s,t=some[0],some[1]
    if ANS[s][t]<10**20:
        print(int(ANS[s][t])-1)
    else:
        print(-1)

Submission status: Wrong Answer

Solution code:
n,m,l=map(int,input().split())
cost=[[10**9+1]*n for i in range(n)]
length=[[(10**9,-l)]*n for i in range(n)]
for i in range(m):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    cost[a][b]=c
    cost[b][a]=c
for i in range(n):
    length[i][i]=(0,-l)
q=int(input())
st=[map(int,input().split())for i in range(q)]

for k in range(n):
    for i in range(n):
        for j in range(n):
            ch,oil=length[i][k]
            oil*=-1
            oilcost=cost[k][j]
            if oilcost>l:
                continue
            new = (ch+1,-(l-oilcost)) if oil<oilcost else (ch,-(oil-oilcost))
            length[i][j]=min(length[i][j],new)
for s,t in st:
    ch=min(length[s-1][t-1][0],length[t-1][s-1][0])
    print(-1 if ch>10**8 else ch)