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:
# -*- coding: utf-8 -*-
"""
Created on Sat Apr 20 20:47:47 2019

@author: Owner
"""

import numpy as np
import sys
import collections
import scipy.misc
import math
from operator import itemgetter
import itertools
import copy
import bisect
import heapq

#素因数を並べる
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   
# 桁数を吐く
def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
def getNearestValueIndex(list, num):
    """
    概要: リストからある値に最も近い値のインデックスを取得する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

def find_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]
    


def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d
# cook your dish here
def dijkstra_back(s,t,n,w,cost):
    #sからtへの最短経路の経路復元
    prev = [s] * n #最短経路の直前の頂点
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
        
        for i in range(n):
            if d[i] > d[v] + cost[v][i]: 
                d[i] = d[v] + cost[v][i]
                prev[i] = v
        
    path = [t]
    while prev[t] != s:
        path.append(prev[t])
        prev[t] = prev[prev[t]]
    path.append(s)
    path = path[::-1]
    return path

N, M, L = list(map(int, input().split()))
cost = [[float("inf") for i in range(N)] for i in range(N)] 

#cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
for m in range(M):
    x,y,z = map(int,input().split())
    cost[x-1][y-1] = z
    cost[y-1][x-1] = z
    
Q = int(input())
S = [0]*Q
T = [0]*Q
for q in range(Q):
    S[q], T[q] = list(map(int, input().split()))
    S[q] -= 1
    T[q] -= 1



def main(): 
    for q in range(Q):
        #print(dijkstra_back(S[q], T[q], N, M, cost))
        root = dijkstra_back(S[q], T[q], N, M, cost)
        fuel = L
        res = 0
        for n in range(len(root)-1):
            fuel -= cost[root[n]][root[n+1]]
            if fuel < 0:
                fuel = L - cost[root[n]][root[n+1]]
                if fuel < 0:
                    print(-1)
                    break
                res+=1
        if fuel < 0:
            continue
        else:
            print(res)
        
                
                
                
            
            
                

    
if __name__ == '__main__':
    main()



"""
N, X = map(int, input().split())

x = list(map(int, input().split()))

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())


all(nstr.count(c) for c in '753')

# 複数配列を並び替え
ABT = zip(A, B, totAB)
# itemgetterには何番目の配列をキーにしたいか渡します
A, B, totAB = zip(*ABT)

# 2進数のbit判定
(x >> i) & 1

# dp最小化問題
dp = [np.inf]*N
for n in range(N):
    if n == 0:
        dp[n] = 0
    else:
        for k in range(1,K+1):
            if n-k >= 0:
                dp[n] = min(dp[n], dp[n-k] + abs(h[n]-h[n-k]))
            else:
                break
# 累積和
add = 1 # 問題によって決まる
res = 0
sums = [0]*(len(nums)+1)
for i in range(len(nums)):
    sums[i+1] = sums[i] + nums[i]
for i in range(0, len(nums), 2):
    left = i
    right = min(i+add, len(nums))
    tmp = sums[right] - sums[left]
    res = max(tmp, res)

#２分探索
li, ri = bisect.bisect_left(p_ac, l[i]-1), bisect.bisect_right(p_ac, r[i]-1)    

#ソート関数
org_list = [3, 1, 4, 5, 2]
new_list = sorted(org_list)
print(org_list)
print(new_list)
# [3, 1, 4, 5, 2]
# [1, 2, 3, 4, 5]

#Distance Transformation
    for h in range(0,H):
        for w in range(0,W):
            if h == 0 and w == 0:
                pass
            elif h == 0:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h-1][W-w]+1)
            elif w == 0:   
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1)
            else:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1, D[H-h-1][W-w]+1, D[H-h][W-w]+2)
            d_max = max(D[H-h-1][W-w-1], d_max)

"""

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[i][0],A[i][1],A[i][2]])

m = len(B)

A = B

# 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):
        if k != i:
            for j in range(n):
                if M[i][j] >= M[i][k]+M[k][j] and j != k:
                    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:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m,l = LI()
    v = [[] for i in range(n)]
    for i in range(m):
        a,b,c = LI()
        a -= 1
        b -= 1
        v[a].append((b,c))
        v[b].append((a,c))
    ans = [[float("inf")]*n for i in range(n)]
    q = []
    for s in range(n):
        heappush(q,(0,s))
        ans[s][s] = 0
        while q:
            dx,x = heappop(q)
            na = ans[s][x]
            for y,w in v[x]:
                if w > l:
                    continue
                nd = dx+w
                na_ = na+(nd > l)
                nd_ = nd if nd < l else w
                if na_ < ans[s][y]:
                    ans[s][y] = na_
                    heappush(q,(nd_,y))
    q = I()
    for _ in range(q):
        s,t = LI()
        s -= 1
        t -= 1
        ds = ans[s][t]
        if ds == float("inf"):
            print(-1)
        else:
            print(ds)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


class Node(object):

  def __init__(self, idx):
    self.idx = idx
    self.supply = 300
    self.remain = 0
    self.edges = []

  def __lt__(self, obj):
    return self.supply > obj.supply or self.remain < obj.supply

  def __gt__(self, obj):
    return self.supply < obj.supply or self.remain > obj.supply

  def __hash__(self):
    return self.idx


def main():
  n, m, tank = map(int, input().split())
  nodes = [Node(i) for i in range(n)]

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

  queries = [list(map(int, input().split())) for _ in range(int(input()))]

  for start, end in queries:
    start -= 1
    end -= 1

    for n in nodes:
      n.supply = 300
      n.remain = 0

    result = -1
    nodes[start].supply = 0
    nodes[start].remain = tank
    currents = set([nodes[start]])

    while len(currents) != 0:
      n = min(currents)
      currents.remove(n)

      if n.idx == end:
        result = n.supply
        break

      for e, d in n.edges:
        if d > tank:
          continue
        elif d > n.remain:
          remain = tank - d
          supply = n.supply + 1
        else:
          remain = n.remain - d
          supply = n.supply

        if e.supply > supply or n.remain < remain:
          e.supply = supply
          e.remain = remain
          currents.add(e)

    print(result)


if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
import sys
n, m, l = map(int, sys.stdin.readline().split())
d = [[10**9] * (n+1) for _ in range(n+1)]
for i in range(n+1):
    d[i][i] = 0
for i in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    if c > l:
        continue
    d[a][b] = c
    d[b][a] = c

q = int(input())
qs = []
for i in range(q):
    s,t = map(int, sys.stdin.readline().split())
    qs.append([s, t])

nex = [[0] * (n+1) for _ in range(n+1)]
for i in range(n+1):
    for j in range(n+1):
        nex[i][j] = j
for k in range(n+1):
    for i in range(n+1):
        for j in range(n+1):
            if d[i][k] + d[k][j] < d[i][j]:
                d[i][j] = d[i][k] + d[k][j]
                nex[i][j] = nex[i][k]

for i in range(q):
    st = qs[i][0]
    gl = qs[i][1]
    hk = 0
    rt = l
    if d[st][gl] == 10**9:
        print(-1)
        continue
    while st != gl:
        np = nex[st][gl]
        rt -= d[st][np]
        if rt < 0:
            hk += 1
            rt = l - d[st][np]
        st = np
    print(hk)

Submission status: Wrong Answer

Solution code:
import collections
import heapq
import sys

input = sys.stdin.readline


def read_i():
    return list(map(int, input().split()))


def read_is(n=1):
    return [read_i() for _ in range(n)]


class Graph:
    def __init__(self, n_nodes):
        self.n_nodes = n_nodes
        self.edges = [[] for _ in range(n_nodes)]

    def add_edge(self, s, t, d=None, undirected=False):
        if d is not None:
            self.edges[s].append((t, d))
        else:
            self.edges[s].append(t)
        if undirected:
            self.add_edge(t, s, d)

    def add_edges(self, edges, undirected=False):
        for edge in edges:
            self.add_edge(*edge, undirected=undirected)


class Dijkstra:
    def __init__(self, graph):
        self.graph = graph

    def compute(self, s, t):
        distances = [float('inf') for _ in range(self.graph.n_nodes)]
        visited = [False for _ in range(self.graph.n_nodes)]
        prev_nodes = [None for _ in range(self.graph.n_nodes)]
        distances[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        while q:
            dist_x, x = heapq.heappop(q)
            if x == t:
                return distances, prev_nodes

            if visited[x]:
                continue
            visited[x] = True

            for y, d_xy in self.graph.edges[x]:
                if visited[y]:
                    continue
                dist_y = dist_x + d_xy
                if dist_y < distances[y]:
                    distances[y] = dist_y
                    prev_nodes[y] = x
                    heapq.heappush(q, (dist_y, y))
        return distances, prev_nodes


n, m, l = read_i()
graph = Graph(n)
costs = collections.defaultdict(int)
for _ in range(m):
    a, b, c = read_i()
    if a > b:
        a, b = b, a
    costs[(a - 1, b - 1)] = c
    graph.add_edge(a - 1, b - 1, d=c, undirected=True)
dijkstra = Dijkstra(graph)
q = int(input())
for _ in range(q):
    s, t = read_i()
    s -= 1
    t -= 1
    distances, prev_nodes = dijkstra.compute(s, t)
    if distances[t] == float('inf'):
        print(-1)
        continue

    ds = []
    node = t
    while node != s:
        prev_node = prev_nodes[node]
        ds.append(costs[tuple(sorted([node, prev_node]))])
        node = prev_node
    ds = ds[::-1]
    count = 0
    r = l
    for x in ds:
        if x > l:
            print(-1)
            break
        r -= x
        if r < 0:
            count += 1
            r = l - x
    else:
        print(count)

Submission status: Wrong Answer

Solution code:
import sys

def solve():
	input=sys.stdin.readline
	n, m, l = map(int, input().split())
	edge = [[] for _ in range(n)]
	for _ in range(m):
		a, b, c = map(int, input().split())
		if c <= l:
			edge[a-1].append((c, b-1))
			edge[b-1].append((c, a-1))
	inf = 10 ** 20
	dist = [[inf for _ in range(n)]for i in range(n)]
	for i in range(n):
		dist[i][i]=0
		for c, b in edge[i]:
			dist[i][b]=c
			
	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])
				
	dist2 = [[n+50 for j in range(n)] for i in range(n)]
	for i in range(n):
		dist2[i][i] = 0
		for j in range(i+1, n):
			if dist[i][j] <= l:
				dist2[i][j] = 1
				dist2[j][i] = 1
	for k in range(n):
		for i in range(n):
			for j in range(n):
				dist2[i][j] = min(dist2[i][k] + dist2[k][j], dist2[i][j])
	q = int(input())		
	for i in range(q):
		s, t = map(int, input().split())
		print(dist2[s-1][t-1] - 1)
	return 0
	
if __name__ == '__main__':
	solve()

Submission status: Wrong Answer

Solution code:
from itertools import permutations
import heapq

inf = float('INF')

def dijkstra(ad_lst, n, s, l):
    costs = [inf for i in range(n)]
    costs[s], Q = 0, []
    heapq.heappush(Q, [0, s])

    while(Q != []):
        acc, u = heapq.heappop(Q)
        for v, c in ad_lst[u].items():
            if c > l:
                continue
            to_cost = 0
            if acc + c > l:
                to_cost = 1
                c -= acc
            if costs[u] + to_cost < costs[v] and costs:
                heapq.heappush(Q, [acc + c, v])
                costs[v] = costs[u] + to_cost
    return costs

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

route = {i:{} for i in range(n)}
for _ in range(m):
    a,b,c = map(int, input().split())
    route[a-1][b-1] = route[b-1][a-1] = c

p_route = []
for i in range(n):
    p_route.append(dijkstra(route, n, i, l))

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

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:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


class Node(object):

  def __init__(self, idx):
    self.idx = idx
    self.supply = 300
    self.remain = 0
    self.edges = []

  def __gt__(self, obj):
    return self.supply > obj.supply or self.remain < obj.supply

  def __lt__(self, obj):
    return self.supply < obj.supply or self.remain > obj.supply

  def __hash__(self):
    return self.idx


def main():
  n, m, tank = map(int, input().split())
  nodes = [Node(i) for i in range(n)]

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

  queries = [list(map(int, input().split())) for _ in range(int(input()))]

  for start, end in queries:
    start -= 1
    end -= 1

    for n in nodes:
      n.supply = 300
      n.remain = 0

    result = -1
    nodes[start].supply = 0
    nodes[start].remain = tank
    currents = set([nodes[start]])

    while len(currents) != 0:
      n = min(currents)
      currents.remove(n)

      if n.idx == end:
        result = n.supply
        break

      for e, d in n.edges:
        if d > tank:
          continue
        elif d > n.remain:
          remain = tank - d
          supply = n.supply + 1
        else:
          remain = n.remain - d
          supply = n.supply

        if e.supply > supply or n.remain < remain:
          e.supply = supply
          e.remain = remain
          currents.add(e)

    print(result)


if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**5)

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())
	a-=1
	b-=1
	G[a].append([b,c])
	G[b].append([a,c])

Q=int(input())
st = []
for i in range(Q):
	s,t=map(lambda x:int(x)-1,input().split())
	st.append([s,t])


T = [[-1]*N for i in range(N)]
seen=[0]*N

for i in range(N):
	T[i][i]=0



def dfs(p,x):
	seen[x]=1
	for i,c in G[x]:
		if i!=p and seen[i]!=1:
			dfs(x,i)
	
	for i,c in G[x]:
		if T[x][i] == -1:
			T[x][i]=c
		else:T[x][i]=min(T[x][i], c)
		
		for j in range(N):
			if T[i][j]!=-1:
				if T[x][j]==-1:
					T[x][j]=T[i][j]+c
					T[j][x]=T[i][j]+c
				else:
					T[x][j] = min(T[i][j]+c,T[x][j])
					T[j][x] = min(T[i][j]+c,T[x][j])


dfs(-1,0)


for i in range(Q):
	u = T[st[i][0]][st[i][1]]
	print(-1 if u<0 else int((u-0.1)//L))

Submission status: Wrong Answer

Solution code:
import numpy as np
#from scipy.sparse.csgraph import csgraph_from_dense
from scipy.sparse.csgraph import dijkstra
 
import sys
input = sys.stdin.readline

[N,M,L]=list(map(int,input().split()))
abc=[list(map(int,input().split())) for _ in range(M)]
Q=int(input())
st=np.array([list(map(int,input().split())) for _ in range(Q)])

if M==0:
  for _ in range(Q):
    print(-1)
    exit()

g=np.zeros((N,N))
for road in abc:
  if road[2]<=L:
    g[road[0]-1][road[1]-1]=road[2]
    g[road[1]-1][road[0]-1]=road[2]

for item in st:
  #csg=csgraph_from_dense(g,null_value=0) #重み0==ノードなし，とする
  #print(item)
  (d,path) = dijkstra(g,
               indices = item[0]-1,
               return_predecessors=True)
  #print(d,path)
  
  shouhi=[]
  s=item[1]-1
  while s!=-9999:
    shouhi.append(d[s])
    s=path[s]
  shouhi=[shouhi[-i-1]-shouhi[-i] for i in range(1,len(shouhi))]
  #print(shouhi)
  if shouhi==[]:
    print(-1)
    continue
  ans=0
  lim=L
  for temporary_shouhi in shouhi:
    if lim<temporary_shouhi:
      lim=L
      ans=ans+1
      lim=lim-temporary_shouhi
    else:
      lim=lim-temporary_shouhi
  print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

N, M, L = map(int, input().split())
v = [[] for _ in range(N)]
for _ in range(M) :
    A, B, C = map(int, input().split())
    if C > L :
        continue
    v[A-1].append((B-1, C))
    v[B-1].append((A-1, C))
    
Q = int(input())


start = defaultdict(lambda : [])
for i in range(Q) :
    s, t = map(int, input().split())
    start[s-1].append((t-1, i))
    
ret = [-1] * Q
for s, d in start.items() :
    # print(s, d)
    dist = [float('inf')] * N
    pre1 = [-1] * N
    pre2 = [-1] * N
    dist[s] = 0
    pre1[s] = L #のこりのガソリン
    pre2[s] = 0 #補充回数
    queue = deque([(s, 0)])
    while queue :
        # print(queue)
        cur, cost = queue.popleft()
        if dist[cur] < cost :
            continue
        for nex, c in v[cur] :
            if cost + c < dist[nex] :
                dist[nex] = cost + c
                # ガソリンが足りるとき
                if pre1[cur] >= c :
                    pre1[nex] = pre1[cur] - c
                    pre2[nex] = pre2[cur]
                # ガソリンが足りないとき
                else :
                    pre1[nex] = L - c
                    pre2[nex] = pre2[cur] + 1
                    
                queue.append((nex, cost + c))
                
    # print(pre1)
    # print(pre2)
    # print()
    
    for dest, i in d :
        ret[i] = pre2[dest]
        
for r in ret :
    print(r)

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
                    if t > i:
                        cost[t][i] = (gas//L+1)*L+c
                    queue.append(t)
            else:
                if gas+c < cost[i][t]:
                    cost[i][t] = gas+c
                    if t > i:
                        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:
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

    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
        if now < 0:
            ans = -1
            break
    print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, L, ABC, Q, ST):

    g = defaultdict(dict)
    for a, b, c in ABC:
        g[a][b] = c
        g[b][a] = c
    
    def f(s, t):
        q = [(0, s)]
        done = set([s])
        d = 0
        while q:
            d, u = heapq.heappop(q)
            qq = [(L, u)]
            cand = set([u])
            while qq:
                rem, uu = heapq.heappop(qq)
                for vv in g[uu]:
                    if rem-g[uu][vv] < 0:
                        continue
                    if vv in cand or vv in done:
                        continue
                    qq.append((rem-g[uu][vv], vv))
                    cand.add(vv)
            if t in cand:
                return d
            
            done |= cand
            for v in cand:
                heapq.heappush(q, (d+1, v))
        return -1

    for s, t in ST:
        print(f(s, t))



def main():
    N, M, L = read_int_n()
    ABC = [read_int_n() for _ in range(M)]
    Q = read_int()
    ST = [read_int_n() for _ in range(Q)]
    (slv(N, M, L, ABC, Q, ST))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m,l = LI()
    v = [[] for i in range(n)]
    for i in range(m):
        a,b,c = LI()
        a -= 1
        b -= 1
        v[a].append((b,c))
        v[b].append((a,c))
    ans = [[float("inf")]*n for i in range(n)]
    q = []
    for s in range(n):
        heappush(q,(0,s))
        ans[s][s] = 0
        while q:
            dx,x = heappop(q)
            na = ans[s][x]
            for y,w in v[x]:
                nd = dx+w
                na_ = na+(nd > l)
                nd_ = nd if nd < l else w
                if na_ < ans[s][y]:
                    ans[s][y] = na_
                    heappush(q,(nd_,y))
    q = I()
    for _ in range(q):
        s,t = LI()
        s -= 1
        t -= 1
        ds = ans[s][t]
        if ds == float("inf"):
            print(-1)
        else:
            print(ds)
    return

#Solve
if __name__ == "__main__":
    solve()