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

import heapq

INF = float('inf')

def dijkstra(graph, st, L):
    n  = len(graph)
    ds = [(INF, 0)]*n
    ds[st] = (0, -L)
    
    qs = [((0, -L), st)]

    while len(qs) > 0:
        d, nodeId = heapq.heappop(qs)
        
        if d > ds[nodeId]:
            continue
        
        for destId, length in graph[nodeId]:
            if -d[1] < length:
                d2 = (d[0]+1, -(L - length))
            else:
                d2 = (d[0], -(-d[1]-length))

            if ds[destId] > d2:
                ds[destId] = d2
                heapq.heappush(qs, (d2, destId))
                
    return (ds)


def main():
    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))

    d = []
    for i in range(N):
        d.append(dijkstra(G, i, L))

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
inf = float("inf")
sys.setrecursionlimit(1000000)



# from cmath import sqrt
from collections import deque, Counter, OrderedDict,defaultdict
from heapq import nsmallest, nlargest, heapify,heappop ,heappush, heapreplace
# from math import ceil,floor,log,sqrt,factorial,pow,pi,gcd,log10,atan,tan
# from bisect import bisect_left,bisect_right
# import numpy as np

def get_array(): return list(map(int , sys.stdin.readline().strip().split()))
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def input(): return sys.stdin.readline().strip()

def dijkstra(n, graph, start):
    """ Uses Dijkstra's algortihm to find the shortest path between in a graph. """
    dist, parents = [float("inf")] * (n+1), [-1] * (n+1)
    dist[start] = 0

    queue = [(0, start)]
    while queue:
        path_len, v = heappop(queue)
        if path_len == dist[v]:
            for w, edge_len in graph[v]:
                if edge_len + path_len < dist[w]:
                    dist[w], parents[w] = edge_len + path_len, v
                    heappush(queue, (edge_len + path_len, w))

    return dist, parents

n,m,L = get_ints()
mydict = defaultdict(list)
for i in range(m):
    a,b,c = get_ints()
    mydict[a].append((b,c))
    mydict[b].append((a,c))
q = int(input())
while q>0:
    s,t=get_ints()
    petrol = L
    dist, parents = dijkstra(n, mydict, s)
    count = 0
    flag = 0
    while t!=s:
        nxt = parents[t]
        need = -1
        for i in mydict[t]:
            if i[0]==nxt:
                need = i[1]
                break
        if need==-1:
            print(-1)
            exit()
        if petrol<need:
            if need>L:
                print(-1)
                exit()
            else:
                petrol = L-need
                count+=1
                t = nxt
        else:
            t = nxt
            petrol-=need
    print(count)
    q-=1

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)
Q=int(input())
for _ in range(Q):
  S,T=map(int, input().split()) 
  dist_matrix, predecessors = dijkstra(csgraph=graph, directed=False, indices=S-1, return_predecessors=True)
  if predecessors[T-1]<-1:
    l=-1
  else:
    l=dist_matrix[T-1]//L
  print(int(l))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque

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

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

G.sort(key=lambda x: x[2])

path_dic = defaultdict(list)

for a, b, c in G:
    path_dic[a].append((b, c))
    path_dic[b].append((a, c))


fuel = L
for start, end in Query:

    dq = deque([])
    visited = set()
    dq.append([start, fuel, 0])
    ans = -1

    while dq:
        next_node, f, cnt = dq.popleft()
        can = path_dic[next_node]

        if next_node == end:
            ans = cnt
            break

        for node, weight in can:
            if node in visited:
                continue

            if f - weight < 0:
                f = L
                cnt += 1

            dq.append([node, f - weight, cnt])

    print(ans)

Submission status: Wrong Answer

Solution code:
input_list = input().split()
town_num = int(input_list[0])
road_num = int(input_list[1])
tank_max = int(input_list[2])
road_list = []
for _ in range(road_num):
    road_list.append(input().split())
query_num = int(input())
query_list = []
for _ in range(query_num):
    query_list.append(input().split())
for query in query_list:
    sup_tank = 0
    tank = tank_max
    query[0] = int(query[0])
    query[1] = int(query[1])
    query = sorted(query)
    s_town = query[0]
    e_town = query[1]
    if road_list == []:
        print(-1)
        continue
    for road in road_list:
        if int(road[0]) == s_town:
            if tank < int(road[2]):
                sup_tank += 1
                tank = tank_max
            elif tank_max < int(road[2]):
                print(-1)
                break
            tank -= int(road[2])
            if int(road[1]) == e_town:
                print(sup_tank)
                break
            s_town = int(road[1])

Submission status: Wrong Answer

Solution code:
#何とか法, AOJのgrl1c
#初め満杯
import sys
input = sys.stdin.readline
#print = sys.stdout.write

n,m,l =map(int, input().split( ))
Edge = [[] for _ in range(n)]

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

dp = [[[m+3,0] for _ in range(n)] for __ in range(n)]

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

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

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

q = int(input())
ans = []
for i in range(q):
    s,t = map(int, input().split( ))
    if dp[s-1][t-1][0] >m+1:###
        print(-1)
    else:
        print(dp[s-1][t-1][0]-1)
#print(dp)
#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
    
    dd = defaultdict(lambda: -1)
    def f(s, t):
        if (s, t) in dd:
            return dd[(s, t)]
        q = [(0, s)]
        done = set()
        d = 0
        while q:
            d, u = heapq.heappop(q)
            if u in done:
                continue
            done.add(u)
            qq = [(-L, u)]
            cand = set()
            while qq:
                rem, uu = heapq.heappop(qq)
                rem = -rem
                for vv in g[uu]:
                    if rem-g[uu][vv] < 0:
                        continue
                    if vv in done:
                        continue
                    qq.append((-(rem-g[uu][vv]), vv))
                    cand.add(vv)
            
            done |= cand
            for v in cand:
                dd[(s, v)] = d
                heapq.heappush(q, (d+1, v))

        for i in range(1, N+1):
            if i not in done:
                dd[(s, i)] = -1

        return dd[(s, t)]

    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:
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
n, m, l = map(int, input().split())
graph = np.ones((n, n), dtype=np.int64) * np.inf
tmp = np.copy(graph)
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c
    tmp[a - 1][b - 1] = 1
    tmp[b - 1][a - 1] = 1

route = floyd_warshall(graph)
tmp = floyd_warshall(tmp)

q = int(input())
ans = []
for _ in range(q):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    if route[s][t] == np.inf:
        ans.append(-1)
        continue
    dist = int(route[s][t])
    step = int(tmp[s][t]) - 1

    hokyu = dist // l
    if dist % l == 0:
        hokyu -= 1
    if hokyu <= step:
        ans.append(hokyu)
    else:
        ans.append(-1)

print(*ans, sep="\n")

Submission status: Wrong Answer

Solution code:
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    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])
    return d

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

n, w = N, M
d = [[float("inf") for i in range(n)] for i in range(n)] 

#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(w):
    x,y,z = map(int,input().split())
    d[x-1][y-1] = z
    d[y-1][x-1] = z
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
D = warshall_floyd(d)

Q = int(input())
for _ in range(Q):
    s,t = tuple(map(int, input().split()))
    print((D[s-1][t-1]-1)//L)

Submission status: Wrong Answer

Solution code:
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
    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(N+1):
            if dist[i][j] <= L:
                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())
        print(ans[s][t]-1) if ans[s][t] < 10**10 else print(-1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

n, m, l = list(map(int, input().split()))
lines = sys.stdin.readlines()
INF = 10 ** 18

dists = [[(INF, INF)] * n for _ in range(n)]

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

for line in lines[:m]:
    a, b, c = map(int, line.split())
    a -= 1
    b -= 1
    if c > l:
        continue
    dists[a][b] = (0, c)
    dists[b][a] = (0, c)

for k in range(n):
    dk = dists[k]
    for i in range(n):
        di = dists[i]
        cik, uik = di[k]
        if cik == INF:
            continue
        for j in range(n):
            ckj, ukj = dk[j]
            if ckj == 0 and uik + ukj <= l:
                new_dist = (cik + ckj, uik + ukj)
            else:
                new_dist = (cik + ckj + 1, ukj)
            if di[j] > new_dist:
                di[j] = new_dist
# print(*dists, sep='\n')

buf = []

for line in lines[m + 1:]:
    s, t = map(int, line.split())
    dist, _ = dists[s - 1][t - 1]
    buf.append(-1 if dist == INF else dist)

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

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
    
    dd = defaultdict(lambda: -1)
    def f(s, t):
        if (s, t) in dd:
            return dd[(s, t)]
        q = [(0, s)]
        done = set([s])
        d = 0
        while q:
            d, u = heapq.heappop(q)
            if u in done:
                continue
            qq = [(-L, u)]
            cand = set()
            while qq:
                rem, uu = heapq.heappop(qq)
                rem = -rem
                for vv in g[uu]:
                    if rem-g[uu][vv] < 0:
                        continue
                    if vv in done:
                        continue
                    qq.append((-(rem-g[uu][vv]), vv))
                    cand.add(vv)
            
            done |= cand
            for v in cand:
                dd[(s, v)] = d
                heapq.heappush(q, (d+1, v))

        for i in range(1, N+1):
            if i not in done:
                dd[(s, i)] = -1

        return dd[(s, t)]

    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:
N, M, L = map(int, input().split())
edges = [[float('inf') for i in range(N)] for j in range(N)]
for i in range(M):
    A, B, C = map(int, input().split())
    A, B = A-1, B-1
    edges[A][B] = C
    edges[B][A] = C

data = [[None for i in range(N)] for j in range(N)]

# Build up data
def dijkstra(start):
    distances = [(float('inf'), float('inf')) for i in range(N)]
    visited = [False for i in range(N)]
    
    distances[start] = (0, L)
    while True:
        minVertex, minDist = None, (float('inf'), float('inf'))
        for n in range(N):
            if not visited[n] and distances[n] < minDist:
                minVertex = n
                minDist = distances[n]

        if minVertex == None: break

        curVertex = minVertex

        refill, left = distances[curVertex]
        
        if visited[curVertex] or distances[curVertex][0] == float('inf'): break
        visited[curVertex] = True
        
        for neighbour in range(N):
            cost = edges[curVertex][neighbour]
            if cost == float('inf'): continue

            if cost > left and L >= cost:
                distances[neighbour] = min(distances[neighbour], (refill + 1, L - cost))
            elif left >= cost:
                distances[neighbour] = min(distances[neighbour], (refill, left - cost))

    for i in range(N):
        if visited[i]:
            data[start][i] = distances[i][0]
        else:
            data[start][i] = -1

for i in range(N): dijkstra(i)

Q = int(input())
for i in range(Q):
    s, t = map(int, input().split())
    print(data[s-1][t-1])

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]:
                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 Warshall_Floyd(edges,N):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if edges[i][j]>edges[i][k]+edges[k][j]:
                    edges[i][j]=edges[i][k]+edges[k][j]
                    if oil[i][k]<edges[k][j]:
                        oil[i][j]=l-edges[k][j]
                        time[i][j]=time[i][k]+1
                    else:
                        oil[i][j]=oil[i][k]-edges[k][j]
                        time[i][j]=time[i][k]
                    continue
                if edges[i][j]==edges[i][k]+edges[k][j]:
                    flag=(oil[i][k]<edges[k][j])
                    if time[i][j]>time[i][k]+flag:
                        if flag:
                            oil[i][j]=l-edges[k][j]
                            time[i][j]=time[i][k]+1
                        else:
                            oil[i][j]=oil[i][k]-edges[k][j]
                            time[i][j]=time[i][k]
                        continue
                    if oil[i][j]>(l-edges[k][j])*flag+(1-flag)*(oil[i][k]-edges[k][j]):
                        if flag:
                            oil[i][j]=l-edges[k][j]
                            time[i][j]=time[i][k]+1
                        else:
                            oil[i][j]=oil[i][k]-edges[k][j]
                            time[i][j]=time[i][k]
                        continue

                    


  #return edges


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

Submission status: Wrong Answer

Solution code:
#coding:utf-8
import sys
sys.setrecursionlimit(2**31-1)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]

    N,M,L = LMIIS()
    A,B,C = [],[],[]
    from collections import defaultdict
    from copy import copy
    road = defaultdict(dict)

    def insertRoad(a,b,c):
        road[a][b] = c
        road[b][a] = c


    def daikusutora(o,d,remain,count,visited):
        tmp = 10**10
        if road[o].keys() is None:
            return -1
        #print('aaaaaaa',set(road[o].keys()).\
        #    difference(visited))
        for di in set(road[o].keys()).difference(visited):
            visited2 = copy(visited)
            visited2.add(di)
            if di == d:
                if remain >= road[o][d]:
                    return count
                elif L >= road[o][d]:
                    return count + 1
                else:
                    return -1
            else:
                if remain >= road[o][di]:
                    tmp2 = daikusutora(di,d,remain-road[o][di],count,visited2)
                    if tmp2 != -1:
                        tmp =  min(tmp,tmp2)
                elif L >= road[o][di]:
                    tmp2 = daikusutora(di,d,L-road[o][di],count+1,visited2)
                    if tmp2 != -1:
                        tmp =  min(tmp,tmp2)
                
        if tmp == 10**10:
            return -1
        else:
            return tmp
            


    for _ in range(M):
        a,b,c = LMIIS()
        insertRoad(a,b,c)
    Q = II()
    query = []
    for _ in range(Q):
        s,t = LMIIS()
        query.append((s,t))
    for s,t in query:
        print(daikusutora(s,t,L,0,set()))






if __name__ == '__main__':
    main()


'''
5 4 4
1 2 2
2 3 2
3 4 3
4 5 2
3
2 1
3 1
4 1
'''

Submission status: Wrong Answer

Solution code:
from collections import deque

N, M, L = map(int, input().split())
routes = [[] for i in range(N+1)]

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


def bfs(start, goal, full_energy):
    seen = [float('INF')]*(N+1)
    seen[start] = 0
    todo = deque([])
    for to, cost in routes[start]:
        if full_energy - cost >= 0:
            todo.append([to, full_energy-cost, 0])

    while todo:
        now, power, charge = todo.popleft()
        if now == goal:
            return charge

        for nex, cost in routes[now]:
            total_cost = (charge+1)*full_energy + cost - power
            if seen[nex] < total_cost:
                continue
            else:
                seen[nex] = total_cost
            if power - cost >= 0:
                todo.appendleft([nex, power-cost, charge])
            todo.append([nex, full_energy-cost, charge+1])
    return -1


memo = [[-2]*(N+1) for i in range(N+1)]
Q = int(input())
for i in range(Q):
    s, t = map(int, input().split())
    if memo[s][t] == -2:
        count = bfs(s, t, L)
        memo[s][t], memo[t][s] = count, count
        print(count)
    else:
        print(memo[s][t])

Submission status: Wrong Answer

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

availableTowns ={}
for _ in range(m):
    a,b,c = [int(i) for i in input().split()]
    if a not in availableTowns:
        availableTowns[a] = []
    availableTowns[a].append((b,c))

    if b not in availableTowns:
        availableTowns[b] = []
    availableTowns[b].append((a,c))

q = int(input())
qrs = [[int(i) for i in input().split()] for _ in range(q)]


def dfs(start, fuel, history):
##    print('  '*len(history),start,fuel)
    if start == townEnd:
        return 0
    nbrs = availableTowns[start]
    if not nbrs:
        return False

    worked = False
    myMin = 100000000
    for nbr,cst in nbrs:
        if nbr in history or cst>l:
            continue
            
        didRef = 1 if cst>fuel else 0
        
        remFuel = (l if didRef else fuel)-cst
        res = dfs(nbr,remFuel,history + [start])
        
        if res is False:
            continue
        
        worked = True
        refills = didRef + res
        if refills<myMin:
            myMin = refills

    return (myMin if worked else False)

for qr in qrs:
    townStart,townEnd = qr
    times = 0
    possible = False
    minCost = 100000000
    if townStart in availableTowns:
        for town,cost in availableTowns[townStart]:
            if cost>l:
                break
            result = dfs(town, l-cost, [town])
            if result is False:
                continue
            possible = True
            if result<minCost:minCost = result
        print(minCost if possible else -1)
    else:
        print(-1)
##    input('continue?')

Submission status: Wrong Answer

Solution code:
N,M,L = [int(i) for i in input().split()]
togo = [[] for i in range(N)]
for i in range(M):
    A,B,C = [int(i) for i in input().split()]
    togo[A-1].append((B-1,C))
    togo[B-1].append((A-1,C))
Q = int(input())
for q in range(Q):
    s,t = [int(i)-1 for i in input().split()]
    #Djikstra
    dist = [(-10000000000,0) for i in range(N)]#(－補給回数,残り燃料)(大きいほどえらい)
    kakutei = [False]*N
    dist[s] = (0,L)
    kakutei[s] = True
    curpos = s 
    for hoge in range(N):
        curkaisu,curfuel = dist[curpos]
        for p,d in togo[curpos]:
            if kakutei[p]:continue
            if curfuel < d:
                newkaisu = curkaisu - 1
                newfuel = L-d
            else:
                newkaisu = curkaisu
                newfuel = curfuel-d
            if (newkaisu,newfuel)>dist[p]:
                dist[p] = (newkaisu,newfuel)
        curmax = (-1,(-100000,0))
        for p,distance in enumerate(dist):
            if kakutei[p]:continue
            if curmax[1]<distance:
                curmax = (p,distance)
        kakutei[curmax[0]] = True
        curpos = curmax[0]
    print(-dist[t][0])

Submission status: Wrong Answer

Solution code:
n, m, l = [int(x) for x in input().split()]
ws      = {}
ds      = {}
ps      = {}

for i in range(0, m):
	x, y, z    = [int(a) for a in input().split()]
	ws[(x, y)] = z
	ws[(y, x)] = z

for i in range(1, n + 1):
	for j in range(1, n + 1):
		if (i, j) in ws:
			ds[(i, j)] = ws[(i, j)]
			ds[(j, i)] = ws[(j, i)]
		else:
			ds[(i, j)] = 10 ** 20
			ds[(j, i)] = 10 ** 20
		ps[(i, j)] = [i, j]
		ps[(j, i)] = [j, i]
		
for k in range(1, n + 1):
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			if ds[(i, k)] + ds[(k, j)] < ds[(i, j)]:
				ds[(i, j)] = ds[(i, k)] + ds[(k, j)]
				ps[(i, j)] = ps[(i, k)] + ps[(k, j)][1:]

q = int(input())

for _ in range(0, q):
	s, t = [int(x) for x in input().split()]
	p    = ps[(s,t)]
	e    = l
	c    = 0
	f    = True
	
	for j in range(1, len(p)):
		d = ds[(p[j - 1], p[j])]
		
		if l < d:
			f = False
			break
		elif e < d:
			e  = l
			c += 1
		
		e -= d
		
	print(c if f else -1)

Submission status: Wrong Answer

Solution code:
import sys
from heapq import *
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    n, m, l = map(int, input().split())
    to = defaultdict(list)
    for _ in range(m):
        a, b, c = map(int, input().split())
        a, b = a - 1, b - 1
        to[a].append((b, c))
        to[b].append((a, c))
    q = int(input())
    st = []
    idx = [[-1] * n for _ in range(n)]
    qc = [0] * n
    for i in range(q):
        s, t = map(int, input().split())
        s, t = s - 1, t - 1
        idx[s][t] = i
        qc[min(s, t)] += 1

    #for x in idx:
        #print(x)
    #print(qc)

    ans = [-1] * q
    for s in range(n):
        #print(ans)
        cnt = qc[s]
        if cnt == 0: continue
        hp = []
        heappush(hp, (0, -l, s))
        fin = [False] * n
        while cnt > 0 and hp:
            k, g, u = heappop(hp)
            if fin[u]: continue
            fin[u] = True
            g = -g
            i = idx[s][u]
            if i != -1:
                ans[i] = k
                idx[s][u] = -1
                cnt -= 1
            i = idx[u][s]
            if i != -1:
                ans[i] = k
                idx[u][s] = -1
                cnt -= 1
            for ku, c in to[u]:
                if fin[ku]: continue
                if g - c >= 0:
                    heappush(hp, (k, c - g, ku))
                else:
                    heappush(hp, (k + 1, -l + c, ku))
    print(*ans)

main()