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 sys
import collections
import math
from operator import itemgetter
import copy
import bisect


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()

Submission status: Wrong Answer

Solution code:
import math
def main():
    INF = int(1e10)
    N, M, L = [int(n) for n in input().split()]
    d = [[INF]*N for i in range(N)]
    lst = [[0] * N for i in range(N)]
    for j in range(N):
        for  i in range(N):
            lst[i][j] = j
    for i in range(N):
        d[i][i] = 0
    for i in range(M):
        a, b, c = [int(n) for n in input().split()]
        a, b = a-1, b-1
        d[a][b] = d[b][a] = c
    
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if d[i][k] + d[k][j] < d[i][j]:
                    d[i][j] = d[i][k] + d[k][j]
                    lst[i][j] = lst[i][k]
    Q = int(input())
    # print(d)
    # print(lst)
    res = []
    for _ in range(Q):
        s, t = [int(n) for n in input().split()]
        res.append(cnt(lst, d, s-1, t-1, 0, L, L))
    for i in res:
        print(i)

def cnt(lst, d, s, t, did, now,  L):
    # print(s, t, did, now)
    # print("-----")
    if lst[s][t] == t:
        if d[s][t] > now:
            if d[s][t] <= L:
                return did + 1
                # return did + math.ceil((d[s][t] - now) / L)
            else:
                return -1
        else:
            return did
    
    nxt = lst[s][t]
    if d[s][nxt] > now:
        if d[s][nxt] <= L:
            do = 1
            # do = math.ceil((d[s][nxt] - now) / L)
            did = did + do
            now = L - d[s][nxt]
            return cnt(lst, d, nxt, t, did, now, L)
        else:
            return -1
    else:
        return cnt(lst, d, nxt, t, did, now - d[s][nxt], L)

main()

Submission status: Wrong Answer

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


def main():
    mod = 10**10
    N, M, L = map(int, input().split())
    dist = [[float('inf') for _ in range(N+1)] for _ in range(N+1)]
    ans = [[float('inf') for _ in range(N+1)] for _ in range(N+1)]
    for i in range(1, N+1):
        dist[i][i] = 0
        ans[i][i] = 1
    for _ in range(M):
        a, b, c = map(int, input().split())
        if c <= L:
            dist[a][b] = c
            dist[b][a] = c

    for i in range(1, N+1):
        for j in range(1, N+1):
            for k in range(1, N+1):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    for i in range(1, N+1):
        for j in range(1, N+1):
            if dist[i][j] <= L and i != j:
                ans[i][j] = 1
    for i in range(1, N+1):
        for j in range(1, N+1):
            for k in range(1, N+1):
                ans[i][j] = min(ans[i][j], ans[i][k] + ans[k][j])

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


class Node(object):

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

  # def __str__(self):
  #  return (f'{self.idx}: {self.supply}/{self.remain} - ' +
  #          ','.join(f'{e.idx}({d})' for e, d in self.edges))


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

  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()))]
  results = [[None] * len(nodes) for _ in range(len(nodes) - 1)]

  for start in range(len(nodes) - 1):
    for n in nodes:
      n.fixed = False
      n.supply = 300
      n.remain = 0

    nodes[start].supply = 0
    nodes[start].remain = tank

    while True:
      node = min([n for n in nodes if not n.fixed], key=lambda n: (n.supply, -n.remain))
      node.fixed = True

      if node.idx == len(nodes) - 1:
        break

      for e, d in node.edges:
        if e.fixed or d > tank:
          continue

        if d > node.remain:
          remain = tank - d
          supply = node.supply + 1
        else:
          remain = node.remain - d
          supply = node.supply

        if e.supply > supply or e.remain < remain:
          e.supply = supply
          e.remain = remain

    for end in range(len(nodes)):
      results[start][end] = nodes[end].supply

  for start, end in queries:
    if results[start - 1][end - 1] == 300:
      print(-1)
    else:
      print(results[start - 1][end - 1])


if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
n, m, L = [int(x) for x in input().split()]
from collections import defaultdict

class Graph():
    def __init__(self):
        """
        self.edges is a dict of all possible next nodes
        e.g. {'X': ['A', 'B', 'C', 'E'], ...}
        self.weights has all the weights between two nodes,
        with the two nodes as a tuple as the key
        e.g. {('X', 'A'): 7, ('X', 'B'): 2, ...}
        """
        self.edges = defaultdict(list)
        self.weights = {}
    
    def add_edge(self, from_node, to_node, weight):
        # Note: assumes edges are bi-directional
        self.edges[from_node].append(to_node)
        self.edges[to_node].append(from_node)
        self.weights[(from_node, to_node)] = weight
        self.weights[(to_node, from_node)] = weight
        
graph = Graph()


adj = []
for i in range(n + 1):
    te = []
    for j in range(n + 1):
        te.append(0)
    adj.append(te)
edges = []
for i in range(m):
    a, b, c = [int(x) for x in input().split()]
    edges.append((a, b, c))
    adj[a][b] = c
    adj[b][a] = c

for edge in edges:
    graph.add_edge(*edge)

def dijsktra(graph, initial, end):
    # shortest paths is a dict of nodes
    # whose value is a tuple of (previous node, weight)
    shortest_paths = {initial: (None, 0)}
    current_node = initial
    visited = set()
    
    while current_node != end:
        visited.add(current_node)
        destinations = graph.edges[current_node]
        weight_to_current_node = shortest_paths[current_node][1]

        for next_node in destinations:
            weight = graph.weights[(current_node, next_node)] + weight_to_current_node
            if next_node not in shortest_paths:
                shortest_paths[next_node] = (current_node, weight)
            else:
                current_shortest_weight = shortest_paths[next_node][1]
                if current_shortest_weight > weight:
                    shortest_paths[next_node] = (current_node, weight)
        
        next_destinations = {node: shortest_paths[node] for node in shortest_paths if node not in visited}
        if not next_destinations:
            return -1
        # next node is the destination with the lowest weight
        current_node = min(next_destinations, key=lambda k: next_destinations[k][1])
    
    # Work back through destinations in shortest path
    path = []
    while current_node is not None:
        path.append(current_node)
        next_node = shortest_paths[current_node][0]
        current_node = next_node
    # Reverse path
    path = path[::-1]
    return path

q = int(input())
while q:
    q -= 1
    ans = 1
    l = L
    coun = 0
    s, t = [int(x) for x in input().split()]
    dik = dijsktra(graph, s, t)
    # print(dik)
    if dik == -1: print(-1)
    else:
        for i in range(len(dik) - 1):
            cc = adj[dik[i]][dik[i + 1]]
            if cc > L:
                ans = 0
                break
            elif cc > l:
                coun += 1
                l = L
            
            l -= cc
                # if l < 0:
                #     coun += 1
                #     l = L
        if ans: print(coun)
        else: print(-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.fixed = False
    self.supply = 300
    self.remain = 0
    self.edges = []

  # def __str__(self):
  #  return (f'{self.idx}: {self.supply}/{self.remain} - ' +
  #          ','.join(f'{e.idx}({d})' for e, d in self.edges))


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

  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))

  results = [[None] * len(nodes) for _ in range(len(nodes) - 1)]

  for start in range(len(nodes) - 1):
    for n in nodes:
      n.fixed = False
      n.supply = 300
      n.remain = 0

    nodes[start].supply = 0
    nodes[start].remain = tank

    while True:
      node = min([n for n in nodes if not n.fixed], key=lambda n: (n.supply, -n.remain))
      node.fixed = True

      if node.idx == len(nodes) - 1:
        break

      for e, d in node.edges:
        if e.fixed or d > tank:
          continue

        if d > node.remain:
          remain = tank - d
          supply = node.supply + 1
        else:
          remain = node.remain - d
          supply = node.supply

        if e.supply > supply or e.remain < remain:
          e.supply = supply
          e.remain = remain

    for end in range(len(nodes)):
      results[start][end] = nodes[end].supply

  for _ in range(int(input())):
    start, end = map(int, input().split())
    print(results[start - 1][end - 1])


if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
import numpy as np

N,M,L=map(int, input().split())
graph=np.zeros((N,N),int)
for _ in range(M):
    A,B,C=map(int, input().split())
    if C<=L:
      graph[A-1,B-1]=C
      graph[B-1,A-1]=C
        
graph = csr_matrix(graph)
dist_matrix, predecessors = dijkstra(csgraph=graph, directed=False, return_predecessors=True)
Q=int(input())
for _ in range(Q):
  S,T=map(int, input().split()) 
  
  if predecessors[S-1,T-1]<-1:
    l=-1
  else:
    l=(dist_matrix[S-1,T-1]-L-0.5)//L
    if l<0:
      l=0

  print(int(l))

Submission status: Wrong Answer

Solution code:
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

################################
n,w,l = map(int,input().split()) #n:頂点数　w:辺の数

cost = [[float("inf") for i in range(n)] for i in range(n)] 
#cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
for i in range(w):
    x,y,z = map(int,input().split())
    cost[x-1][y-1] = z
    cost[y-1][x-1] = z
    
Q = int(input())
for q in range(Q):
    s, t = map(int, input().split())
    di = dijkstra(s-1,n,w,cost)
    print(di[t-1]//l)

Submission status: Wrong Answer

Solution code:
n,m,l=map(int,input().split())
inf=float("inf")
f=[[2*[inf]for _ in range(n)]for _ in range(n)]
for i in range(n):f[i][i][1]=0
for i in range(m):
  a,b,c=map(int,input().split())
  if c>l:continue
  f[a-1][b-1][1]=f[b-1][a-1][1]=1
  f[a-1][b-1][0]=f[b-1][a-1][0]=c
for i in range(n):
  for j in range(n):
    for k in range(n):
      a=f[i][j][1]
      b=f[i][k][1]+f[k][j][1]
      if f[i][k][0]+f[j][k][0]<=l:b-=1
      if a>b:
        f[i][j][1]=b
        f[i][j][0]=f[k][j][0]
      elif a==b:
        if f[k][j][0]<f[i][j][0]:f[i][j][0]=f[k][j][0]
for i in range(int(input())):
  s,t=map(int,input().split())
  if f[s-1][t-1][1]==inf:print(-1)
  else:print(f[s-1][t-1][1]-1)

Submission status: Wrong Answer

Solution code:
import sys

N,M,L=map(int, sys.stdin.readline().split())

d=[  [ float("inf") for j in range(N+1) ]  for i in range(N+1) ]

for _ in range(M):
    a,b,c=map(int, sys.stdin.readline().split())
    d[a][b]=c
    d[b][a]=c
    d[a][a]=0
    d[b][b]=0

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


Q=input()
st=[ map(int, sys.stdin.readline().split()) for _ in range(Q) ]

for s,t in st:
    if d[s][t]==float("inf"):
        print -1
    if d[s][t]%L==0:
        print d[s][t]/L
    else:
        print d[s][t]/L+1

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from heapq import heappop, heappush


class Graph(object):
  
    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):

    def __init__(self, graph, start,l):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if dist_u != 0:
                  if (dist_u - 1) // l != (alt - 1) // l:
                    alt = ((dist_u - 1) // l + 1) * l + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        if self.dist[goal] == float("inf"):
          return -1
        return self.dist[goal] // l

    def shortest_path(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

n,m,l = map(int, input().split())
abc = [list(map(int, input().split())) for i in range(m)]
q = int(input())
st = [list(map(int, input().split())) for i in range(q)]
path = Graph()
for i in abc:
  a,b,c = i[0], i[1], i[2]
  if c <= l:
    path.add_edge(a-1, b-1, c)
    path.add_edge(b-1, a-1, c)
for i in st:
  s,t = i[0]-1, i[1]-1
  s_path = Dijkstra(path, s, l)
  ans = s_path.shortest_distance(t)
  print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools

import queue
from collections import deque



def main():
    node_num, edge_num, max_tank = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(edge_num)]
    q_num = int(input())
    query = [list(map(int, input().split())) for i in range(q_num)]

    graph_data = defaultdict(set)
    dist_data = defaultdict(int)

    for i in range(edge_num):
        a, b, c = data[i]
        graph_data[a].add(b)
        graph_data[b].add(a)
        dist_data[(a, b)] = c
        dist_data[(b, a)] = c

    ans_list = [[-1 for i in range(node_num + 1)] for j in range(node_num + 1)]

    for i in range(1, node_num + 1):
        ans_list[i][i] = (0, max_tank)

        count_all = node_num - 1

        check_ele = set()
        check_ele.add(i)
        for j in range(1, i):
            if ans_list[j][i] == -1:
                continue
            count_all -= 1
            ans_list[i][j] = ans_list[j][i]
            check_ele.add(j)
        aaa = []

        for bbb in check_ele:
            for next_ele in graph_data[bbb]:
                if ans_list[i][next_ele] != -1:
                    continue

                count_data, nokori_data = ans_list[i][bbb]

                dist = dist_data[(bbb, next_ele)]
                if dist > max_tank:
                    continue
                if dist <= nokori_data:
                    heapq.heappush(aaa, (count_data, - (nokori_data - dist), next_ele))
                else:
                    heapq.heappush(aaa, (count_data + 1, - (max_tank - dist), next_ele))

        while len(aaa):
            count, nokori, now_ele = heapq.heappop(aaa)

            if ans_list[i][now_ele] != -1:
                continue

            nokori = -1 * nokori
            ans_list[i][now_ele] = (count, nokori)
            count_all -= 1

            if count_all == 0:
                break

            for next_ele in graph_data[now_ele]:
                if ans_list[i][next_ele] != -1:
                    continue
                dist = dist_data[(now_ele, next_ele)]
                if dist > max_tank:
                    continue
                if nokori < dist:
                    heapq.heappush(aaa, (count + 1, - (max_tank - dist), next_ele))
                else:
                    heapq.heappush(aaa, (count, - (nokori - dist), next_ele))



    for i in range(q_num):
        s, t = query[i]
        ans = ans_list[s][t]
        if ans == -1:
            print(-1)
        else:
            print(ans[0])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def solve():
    from heapq import heappush, heappop
    import sys
    input = sys.stdin.readline

    INF = float('inf')

    # 単一始点最短経路を求める（Dijkstra法）
    def Dijkstra(adjList, vSt):
        numV = len(adjList)
        useds = [False] * numV
        numUsed = 0
        costs = [[INF, 0, INF] for _ in range(numV)]
        costs[vSt] = [0, -L, 0]
        while True:
            cNow, vNow = [INF, 0, INF], -1
            for v in range(numV):
                if useds[v]: continue
                if costs[v] < cNow:
                    cNow, vNow = costs[v], v
            useds[vNow] = True
            numUsed += 1
            if numUsed == numV: break
            fuel = -costs[vNow][1]
            for v2, wt in adjList[vNow]:
                if useds[v2]: continue
                f2 = fuel-wt
                c2 = list(cNow)
                c2[2] += wt
                if f2 >= 0:
                    c2[1] = -f2
                else:
                    c2[0] += 1
                    c2[1] = -(L-wt)
                if c2 < costs[v2]:
                    costs[v2] = c2
        return costs


    N, M, L = map(int, input().split())
    adjL = [[] for _ in range(N)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        A, B = A-1, B-1
        adjL[A].append((B, C))
        adjL[B].append((A, C))
    Q = int(input())
    querys = [tuple(map(int, input().split())) for _ in range(Q)]

    numss = []
    for v in range(N):
        costs = Dijkstra(adjL, v)
        numss.append([num for num, f, c in costs])

    anss = []
    for s, t in querys:
        s, t = s-1, t-1
        ans = numss[s][t]
        if ans == INF:
            anss.append(-1)
        else:
            anss.append(numss[s][t])

    print('\n'.join(map(str, anss)))


solve()

Submission status: Wrong Answer

Solution code:
def dijkstra(s,t,n,w,cost):
    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[t]

n,w,l = map(int,input().split())
cost = [[float("inf") for i in range(n)] for i in range(n)] 
for i in range(w):
    x,y,z = map(int,input().split())
    cost[x-1][y-1] = z
    cost[y-1][x-1] = z

Q = int(input())
for j in range(Q):
    p,q = map(int,input().split())
    tmp = dijkstra(p-1,q-1,n,w,cost)
    print(-1 if str(tmp)=="inf" else (tmp // l))

Submission status: Wrong Answer

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

abc = [[0 for i in range(N)] for j in range(N)]

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

Q = int(input())
for i in range(Q):
    s_t, t_t = map(int, input().split())
    s = s_t - 1
    t = t_t - 1
    
    length = abs(s-t)
    if s<t:
        dct = True
    else:
        dct = False
    
    l = L
    
    flag = True
    
    cnt = 0
    
    if dct:
        start = min(s, t)
        for j in range(length):
            if abc[start][start+1]>L or abc[start][start+1]==0:
                flag = False
                break
            elif abc[start][start+1]>l:
                cnt += 1
                l = L
            else:
                l -= abc[start][start+1]
            start += 1
                
                
    else:
        start = max(s, t)
        for j in range(length):
            if abc[start][start-1]>L or abc[start][start-1]==0:
                flag = False
                break
            elif abc[start][start-1]>l:
                cnt += 1
                l = L
            else:
                l -= abc[start][start-1]
            start -= 1
            
            
    if flag:
        print(cnt)
    else:
        print(-1)

Submission status: Wrong Answer

Solution code:
from sys import stdin
def main():
    n, m, l = list(map(int, input().split()))
    a, b, c = [0] * m, [0] * m, [0] * m

    for i in range(m):
        a[i], b[i], c[i] = list(map(int, input().split()))
    
    q = int(input())
    s, t = [0] * q, [0] * q
    for i in range(q):
        s[i], t[i] = list(map(int, input().split()))
    road_list = [{}]*(n+1)
    for i in range(m):
        road_list[a[i]][b[i]] = c[i]
        road_list[b[i]][a[i]] = c[i]
    
    def calc(s , e, parent, fcount, prev_l, l):
        if s == e:
            return True, fcount
        tmplist = road_list[s]
        dlist = tmplist.keys()
        clist = tmplist.values()
        ans = -1
        flag = False
        for cost,item in zip(clist, dlist):
            if item in parent:
                continue
            parent += [s]
            if cost > l:
                continue
            if cost + prev_l > l:
                fcount += 1
                prev_l = 0
            else:
                prev_l = prev_l + cost
            tmpflag, out_f = calc(item, e, parent, fcount, prev_l, l)
            if not flag:
                ans = out_f
            flag = flag or tmpflag
            ans = min(ans, out_f)
        return flag, ans
    for i in range(q):
        f, ans = calc(s[i], t[i], [s], 0, 0, l)
        print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

N,M,L=map(int, sys.stdin.readline().split())

d=[  [ float("inf") for j in range(N+1) ]  for i in range(N+1) ]

for _ in range(M):
    a,b,c=map(int, sys.stdin.readline().split())
    d[a][b]=c
    d[b][a]=c
    d[a][a]=0
    d[b][b]=0

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


Q=input()
st=[ map(int, sys.stdin.readline().split()) for _ in range(Q) ]

for s,t in st:
    if d[s][t]==float("inf"):
        print -1
    else:
        print d[s][t]/L

Submission status: Wrong Answer

Solution code:
n,m,l=map(int,input().split())
f=[[2*[float("inf")]for _ in range(n)]for _ in range(n)]
for i in range(n):f[i][i][1]=0

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

for i in range(n):
  for j in range(n):
    for k in range(n):
      a=f[i][j][1]
      b=f[i][k][1]+f[k][j][1]
      if f[i][k][0]+f[j][k][0]<=l:b-=1
      if a>b:
        f[i][j][1]=b
        f[i][j][0]=f[k][j][0]
      elif a==b:
        if f[k][j][0]<f[i][j][0]:f[i][j][0]=f[k][j][0]

for i in range(int(input())):
  s,t=map(int,input().split())
  if f[s-1][t-1][1]==float("inf"):print(-1)
  else:print(f[s-1][t-1][1]-1)

Submission status: Wrong Answer

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

map_list = [[0]*N for i in range(N)]

for i in range(M):
    a,b,c = map(int,input().split())
    map_list[a-1][b-1] = map_list[b-1][a-1] = c
#print(map_list)
for i in range(int(input())):
    # 幅優先探索でコストを探す
    # ダイクストラ法で探す
    s,t = map(int,input().split())

    arrived_flag = [False] * N
    arrived_flag[s-1] = True
    cost,limit = 0, L
    finish_flag = False
    queue = [s-1]
    queue_l = [limit]
    queue_cnt = [0]
    while queue:

        if finish_flag:
            break

        present_state = queue.pop(0)
        present_limit = queue_l.pop(0)
        present_cnt = queue_cnt.pop(0)

        arrived_flag[present_state] = True #登録
        #終了判定
        if present_state == t-1:
            print(present_cnt)
            finish_flag = True
            #finish
            break

        for i in range(N):
            # 0 じゃなければ 追加
            if map_list[present_state][i] != 0 and arrived_flag[i] != True:

                queue.append(i)
                #給油
                if present_limit < map_list[present_state][i]:
                    # 給油
                    present_cnt += 1
                    limit = L

                limit -= map_list[present_state][i]
                queue_l.append(limit)
                queue_cnt.append(present_cnt)

            #print(queue)
    if not finish_flag:
        print(-1)

Submission status: Wrong Answer

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

def main():
    input = sys.stdin.readline
    N, M, L = map(int, input().split())
    inf = 10**9 + 1
    d = [[inf] * N for _ in range(N)]
    connect = [[] for _ in range(N)]
    for i in range(N):
        d[i][i] = 0
    for _ in range(M):
        a, b, c = map(int, input().split())
        d[a-1][b-1] = c
        d[b-1][a-1] = c
        connect[a-1].append(b-1)
        connect[b-1].append(a-1)
    
    ans = [[-1]*N for _ in range(N)]
    def f(s, t, l, cnt):
        for nt in connect[t]:
            if ans[s][nt] != -1 and ans[s][nt] <= cnt:
                continue
            
            if d[t][nt] > l:
                cnt += 1
                l = L
            else:
                l -= d[t][nt]
            
            if ans[s][nt] > cnt or ans[s][nt] == -1:
                ans[s][nt] = cnt
                ans[nt][s] = cnt
                f(s, nt, l, cnt)
            
            f(nt, nt, L, 0)
    
    f(0, 0, L, 0)
    
    Q = int(input())
    for _ in range(Q):
        s, t = map(int, input().split())
        print(ans[s-1][t-1])
    
    exit()


if __name__ == '__main__':
    print(main())