Problem:


Score : 500 points

Problem Statement

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

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

Process the following Q queries:

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

Constraints

All values in input are integers.

2 \leq N \leq 300

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

1 \leq L \leq 10^9

1 \leq A_i, B_i \leq N

A_i \neq B_i

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

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

1 \leq C_i \leq 10^9

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

1 \leq s_i, t_i \leq N

s_i \neq t_i

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

Input

Input is given from Standard Input in the following format:

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

Output

Print Q lines.

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

Sample Input 1

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

Sample Output 1

0
1

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

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

Sample Input 2

4 0 1
1
2 1

Sample Output 2

-1

There may be no road at all.

Sample Input 3

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

Sample Output 3

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



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


Sample output:
0
1

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush

class Dijk:
    def __init__(self, n,l):
        self.table = [[] for i in range(n+1)]
        self.n = n+1
        self.l = l
 
    def add(self, x, y, f):
        self.table[x].append((y, f))
 
    def di(self, s):
        inf = float('inf')
        self.val = [inf] * self.n
        self.val[s] = 0
        h = []
        heappush(h, (0, s, self.l))
        while h:
            q, i, ll= heappop(h)
            if self.val[i] < q:
                continue
            for x, c,in self.table[i]:
                if ll-c>=0:
                    if self.val[x] > self.val[i]:
                        self.val[x] = self.val[i]
                        heappush(h, (self.val[x], x,ll-c))
                else:
                    if self.val[x] > self.val[i]+1:
                        self.val[x] = self.val[i]+1
                        heappush(h, (self.val[x], x, self.l-c))
 
    def dist(self, s, t):
        return self.val[t]

n,m,l=map(int,input().split())
load=[[] for i in range(n+1)]

dijk=Dijk(n,l)
for _ in range(m):
    a,b,c=map(int,input().split())
    dijk.add(a,b,c)
    dijk.add(b,a,c)
q=int(input())

for _ in range(q):
    s,t=map(int,input().split())
    dijk.di(s)
    if dijk.dist(s,t)!=float('inf'):
        print(dijk.dist(s,t))
    else:
        print(-1)

Submission status: Wrong Answer

Solution code:
N,M,L = map(int,input().split())
edges = [[] for _ in range(N+1)]
for _ in range(M):
    a,b,c = map(int,input().split())
    if c <= L:
        edges[a].append((b,c))
        edges[b].append((a,c))

newedges = [[] for _ in range(N+1)]
def f(town, cur, used):
    if used > L or seen[cur]:
        return
    seen[cur] = 1
    if town != cur:
        newedges[town].append(cur)
    for neighbour, cost in edges[cur]:
        f(town, neighbour, used+cost)

for v in range(1,N+1):
    seen = [0]*(N+1)
    f(v, v, 0)

Q = int(input())
for _ in range(Q):
    s,t = map(int,input().split())

    seen = [0]*(N+1)
    queue = [[s,-1]]
    success = 0
    while queue:
        town, time = queue.pop(0)
        #print(town, time)
        seen[town] = 1
        if town == t:
            print(time)
            success = 1
            break
        for neighbour in newedges[town]:
            if not seen[neighbour]:
                #print("adding", (neighbour, time+1))
                queue.append([neighbour, time+1])
    if not success:
        print(-1)

Submission status: Wrong Answer

Solution code:
def e_travel_by_car():
    N, M, L = [int(i) for i in input().split()]
    Roads = [[int(i) for i in input().split()] for j in range(M)]
    Q = int(input())
    Queries = [[int(i) for i in input().split()] for j in range(Q)]

    graph = [[float('inf')] * N for _ in range(N)]
    for k in range(N):
        graph[k][k] = 0
    for a, b, c in Roads:
        graph[a - 1][b - 1] = c
        graph[b - 1][a - 1] = c

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

    ans = []
    for s, t in Queries:
        ans.append((graph[s - 1][t - 1] - 1) // L if graph[s - 1][t - 1] != float('inf') else -1)
    return '\n'.join(map(str, ans))

print(e_travel_by_car())

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

def sol():
    N, M, L = map(int, input().split())
    edges = [[] for _ in range(N)]

    for _ in range(M):
        fr, to, cost = map(int, input().split())
        fr -= 1
        to -= 1
        edges[fr].append((to, cost))
        edges[to].append((fr, cost))

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

        Q = set()
        cntList = [(INF, 0, 0)] * N  # cnt, fuel, var
        cntList[start] = (0, L, 0)
        confilm = [False] * N
        confilm[start] =True

        for to, cost in edges[start]:
            if L - cost >= 0:
                Q.add(to)
                cntList[to] = (0, -(L - cost), -2)

        while Q:
            nextNode = (INF, 0, 0)
            now = -1
            for q in Q:
                if nextNode > cntList[q]:
                    nextNode = cntList[q]
                    now = q

            if now == -1:
                break

            if now == end:
                break
            Q.remove(now)
            confilm[now] = True

            for to, cost in edges[now]:
                if confilm[to]:
                    continue

                c, f, v = nextNode
                f *= -1
                v *= -1

                if f - cost < 0:
                    c += 1
                    f = L
                    v -= 1
                    if v < 0 or f < 0:
                        continue

                cntList[to] = min(cntList[to], (c, -(f - cost), -v))
                Q.add(to)

        if cntList[end][0] == INF:
            ans.append(-1)
        else:
            ans.append(cntList[end][0])

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

sol()

Submission status: Wrong Answer

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

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


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

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


def shortestPath(g: Graph, s: int, L: int):
    visited = [False]*g.N

    charge = [INF]*g.N
    charge[s] = 0

    rest = [0]*g.N            # 現在の走行距離

    Q = []
    heapq.heappush(Q, s)

    while len(Q) > 0:
        u = heapq.heappop(Q)
        # print("--", u, "--")
        if visited[u] == True:
            continue
        visited[u] = True
        for v, w in g.E[u]:
            if visited[v]:
                continue
            if rest[u]+w > L:
                c, r = (charge[u]+1, w)
            else:
                c, r = (charge[u], rest[u]+w)
            rest[v] = r
            charge[v] = c
            if visited[v] == False:
                heapq.heappush(Q, v)
            # print((c, r))
    return charge, rest


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

    charges = []
    rests = []
    for i in range(N):
        charge, rest = shortestPath(g, i, L)
        charges.append(charge)
        rests.append(rest)
    # for c, r in zip(charges[0], rests[0]):
    #     print(c, r)
    # return

    for i in range(Q):
        charge, rest = charges[s[i]-1], rests[s[i]-1]
        if charge[t[i]-1] == INF:
            print(-1)
        else:
            print(charge[t[i]-1])

    return


def main():

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
n, m, l = map(int, input().split())
# 距離,直前の頂点
d = [[10 ** 10] * n for _ in range(n)]
nex = [[i for i in range(0, n)] for _ in range(n)]
# print(nex)
for _ in range(m):
    a, b, c = map(int, input().split())
    if c <= l:
        d[a-1][b-1] = c
        d[b-1][a-1] = c

for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]
                nex[i][j] = nex[i][k]
q = int(input())
ans = []
for _ in range(q):
    s, t = map(int, input().split())
    if d[s - 1][t - 1] >= 10 ** 10:
        ans.append(-1)
        continue
    ans.append([s - 1, t - 1, d[s - 1][t - 1], l, (d[s - 1][t - 1]/l)])


def printPath3(start, goal):
    fuel = l
    ans = 0
    cur = start
    while (cur != goal):
        # print(cur)
        fuel -= d[cur][nex[cur][goal]]
        if (fuel < 0):
            ans += 1
            fuel = l-d[cur][nex[cur][goal]]
        cur = nex[cur][goal]
    # print(goal)
    return ans


for i in ans:
    # print(i)
    if i != -1:
        print(printPath3(i[0], i[1]))
    else:
        print(-1)

Submission status: Wrong Answer

Solution code:
import heapq

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

tree=[]
for _ in range(N+1):
  tree.append([])

dist={}
for _ in range(M):
  A,B,C=map(int,input().split())
  tree[A].append(B)
  tree[B].append(A)
  dist[(A,B)]=C
  dist[(B,A)]=C

#print(tree)
#print(dist)

Q=int(input())
for _ in range(Q):
  s,t=map(int,input().split())
  
  dlist=[10**15]*(N+1)
  dlist[s]=0
  prev_list=[-1]*(N+1)
  hq=[]
  for i in range(1,N+1):
    if i==s:
      heapq.heappush(hq,(0,i))
    else:
      heapq.heappush(hq,(10**15,i))
    
  while(len(hq)>0):
    (d,i)=heapq.heappop(hq)
    for j in tree[i]:
      if dlist[j]>dlist[i]+dist[(i,j)]:
        dlist[j]=dlist[i]+dist[(i,j)]
        prev_list[j]=i
  
  #print(dlist)
  #print(prev_list)
  #print(dlist[t])  
  if dlist[t]>10**10:
    print(-1)
  elif dlist[t]<L:
    print(0)
  else:
    answer=0
    energy=L
    tt=t
    while(prev_list[tt]!=-1):
      if dist[(tt,prev_list[tt])]>energy:
        energy=L
        answer+=1
      
      energy-=dist[(tt,prev_list[tt])]
      tt=prev_list[tt]

    print(answer)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n, m, l = [ int(v) for v in input().split() ]
charge_list = [ [ [10**5, 0] for i in range(n) ] for j in range(n) ]
distance_list = [ [ -1 for i in range(n) ] for j in range(n) ]

for i in range(m): 
    a, b, d = [ int(v) for v in input().split() ]
    a, b = a-1, b-1
    if d <= l:
        charge_list[a][b] = [0, l-d]
        charge_list[b][a] = [0, l-d]
        distance_list[a][b] = d
        distance_list[b][a] = d

for k in range(n):
    for i in range(n):
        for j in range(n):
            a = charge_list[i][k][0] + charge_list[k][j][0] 
            if charge_list[i][k][1] + charge_list[k][j][1] >= l:
                b = 0
                c = charge_list[i][k][1] + charge_list[k][j][1] - l
            else:
                b = 1
                c = 0
            if charge_list[i][j][0] >= a+b:
                charge_list[i][j][0] = a+b
                charge_list[i][j][1] = c
            elif charge_list[i][j][0] == a+b and charge_list[i][j][1] > c:
                charge_list[i][j][1] = c

q = int(input())
for i in range(q):
    s, t = [ int(v) for v in input().split() ]
    ans = charge_list[s-1][t-1][0]
    if ans == 100000:
        print(-1)
    else:
        print(charge_list[s-1][t-1][0])

Submission status: Wrong Answer

Solution code:
import sys, math

def input():
    return sys.stdin.readline()[:-1]

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

def main():
    N, M, L = map(int,input().split())
    cost = [[float("inf") for k in range(N)] for j in range(N)]
    for k in range(M):
        A, B, C = map(int,input().split())
        cost[A-1][B-1] = C
        cost[B-1][A-1] = C
    Q = int(input())
    ans = []
    for q in range(Q):
        s, t = map(int,input().split())
        d = dijkstra_back(s-1,t-1,N,M,cost)
        temp = L
        u = 0
        for k in range(len(d)-1):
            if cost[d[k]][d[k+1]] > temp:
                u += 1
                temp = L - cost[d[k]][d[k+1]]
                if temp < 0:
                    u =- 1
                    break
            else:
                temp -= cost[d[k]][d[k+1]]
        ans.append(u)
    print(*ans,sep="\n")


if __name__ == '__main__':
    main()

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,max(c-l,0)]:
                dp[i][j] = [f+1,max(c-l,0)]

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:
import sys

input = sys.stdin.readline

def main():
	N, M, L = list(map(int,input().split()))
	P = [list(map(int,input().split())) for i in range(M)]
	Q = int(input())
	st = [list(map(int,input().split())) for i in range(Q)]

	neighbor = [[] for i in range(N)]
	for pi in P:
		if pi[2]<=L:
			neighbor[pi[0]-1].append((pi[1]-1,pi[2]))
			neighbor[pi[1]-1].append((pi[0]-1,pi[2]))

	start = 0
	end = 2

	def bfs(start, end):
		update = 0
		updatemax = len(neighbor[end])
		fuel = [[10000000,L+1] for i in range(N)]
		fuel[start][0] = 0
		fuel[start][1] = L
		queue = [start]
		while len(queue)>0:
			nq = []						# next target node
			for i in queue:				# target node
				oc, om = fuel[i]
				for j, d in neighbor[i]:	# next node
					if om<d:
						nc = oc+1
						nm = L-d
					else:
						nc = oc
						nm = om-d

					# print(i,j,nc,nm)

					if (nc<fuel[j][0]) or (nc==fuel[j][0] and nm>fuel[j][1]):
						fuel[j][0], fuel[j][1] = nc, nm
						nq.append(j)
						if j==end: update += 1

			if update==updatemax:
				# print('update==updatemax')
				break
			queue = nq					# update target node

		ans = fuel[end][0]
		if fuel[end][0]==10000000: ans = -1

		print(ans)

	for s, t in st:
		start, end = s-1, t-1
		bfs(start,end)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
import collections
import heapq


class Dijkstra():
    def __init__(self):
        self.e = collections.defaultdict(list)
        self.ed = collections.defaultdict(dict)
    def add(self, u, v, d, directed=False):
        if directed is False:
            self.e[u].append([v, d])
            self.e[v].append([u, d])
            self.ed[u][v] = d
            self.ed[v][u] = d
        else:
            self.e[u].append([v, d])
    def delete(self, u, v):
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]
    def Dijkstra_search(self, s):
        d = collections.defaultdict(lambda: float('inf'))
        prev = collections.defaultdict(lambda: None)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in self.e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    prev[uv] = u
                    heapq.heappush(q, (vd, uv))

        return d, prev
    def getDijkstraShortestPath(self, start, goal):
        _, prev = self.Dijkstra_search(start)
        shortestPath = []
        node = goal
        while node is not None:
            shortestPath.append(node)
            node = prev[node]

        return shortestPath[::-1]

n,m,l=map(int,input().split())
edges = {}
graph = Dijkstra()
for _ in range(m):
    a,b,c=map(int,input().split())
    graph.add(a,b,c)
q = int(input())
for _ in range(q):
    s,t=map(int,input().split())
    path = graph.getDijkstraShortestPath(s,t)
    if len(path) == 1:
        print(-1)
        continue
    now = path[0]
    cl = l
    ans = 0
    for to in path[1:]:
        cost = graph.ed[now][to]
        if cl - cost < 0:
            cl = l - cost
            ans += 1
        else:
            cl -= cost
        now = to
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def tami(start, now, cnt, fuel, visited):
  # ans更新
  if cnt < cost[start][now][0]:
    cost[start][now] = [cnt, fuel]
  elif cnt == cost[start][now][0] and fuel < cost[start][now][1]:
    cost[start][now] = [cnt, fuel]

  # dfs
  for x,c in root[now]:
    if str(x) not in visited:
      if fuel - c < 0:
        cnt += 1
        fuel = L
      tami(start, x, cnt, fuel - c, visited + str(x))

N, M, L = IL()
abc = [IL() for i in range(M)]
Q = I()
q = [IL() for i in range(Q)]

root = [[] for i in range(N+1)]
cost = [[[MAX_INT, MAX_INT] for i in range(N+1)] for i in range(N+1)]
for a,b,c in abc:
  if c > L:
    continue
  root[a].append([b, c])
  root[b].append([a, c])
#print(root)

for i in range(1,N+1):
  visited = ""
  tami(i, i, 0, L, visited + str(i))
#print(cost)

for a,b in q:
  ans = cost[a][b][0]
  if ans == MAX_INT:
    print(-1)
  else:
    print(ans)

Submission status: Wrong Answer

Solution code:
#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)]

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, M, L = 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 i in range(M):
    a,b,c = map(int,input().split())
    if c <= L:
      cost[a-1][b-1] = c
      cost[b-1][a-1] = c
#print(dijkstra(0,N,M,cost)) [0, 3, 6]
Q = int(input())
for i in range(Q):
  s,t = map(int,input().split())
  ob = dijkstra(s-1, N, M, cost)[t - 1]
  if ob == "inf":
    print(-1)
  else:
    print(ob // L)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
# debug = True

debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def matdprint(mat):
    if debug == True:
        for i in range(len(mat)):
            for j in range(len(mat[i])):
                print(mat[i][j], end=', ')
            print()

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()

INF = 10 ** 18
MOD = 10 ** 9 + 7
def conv(s):
    cnt = 0
    for n in s:
        cnt += 2**n
    return cnt

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


def nr_warshall_floyd(nr, d, L):
    #nr[i][j]: (iからjへの最短補給回数, iからjへ最短補給回数でやった時の残り燃料)
    n = len(d)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                # そもそもkルートが可能か判断
                if d[k][i] == INF:
                    continue
                if d[j][k] == INF:
                    continue

                # kで補給がいるかの判断
                num_at_k = nr[i][k][0]
                res_at_k = nr[i][k][1]

                # if (i, j) == (0, 4):
                #     dprint(k)
                #     dprint(nr)
                #     dprint(num_at_k, res_at_k)

                num_at_j = num_at_k + nr[k][j][0]
                res_at_j = res_at_k - d[k][j]
                if d[k][j] > res_at_k:
                    # 補給が必要。補給してすすむ
                    num_at_j += 1
                    res_at_j = L - d[k][j]
                else:
                    # 補給がいらない
                    pass

                if num_at_j < nr[i][j][0]:
                    # 採用
                    nr[i][j] = (num_at_j, res_at_j)
                elif num_at_j > nr[i][j][0]:
                    # 不採用
                    pass
                else:
                    # 等しいときは残り燃料で比べる
                    nr[i][j] = (num_at_j, min(nr[i][j][1], res_at_j))
    return nr

def main():

    N, M, L = LI()
    abc_list = []
    for i in range(M):
        a, b, c = LI()
        abc_list.append((a-1,b-1,c)) # 0 origin

    q_list = []
    Q = II()
    for i in range(Q):
        s, t = LI()
        q_list.append((s-1, t-1)) # 0 origin

    # ワーシャルフロイドもどきをやる
    dmx = INF
    nmx = N+1
    d = [[dmx for i in range(N)] for i in range(N)]
    nr = [[(nmx, 0) for i in range(N)] for i in range(N)]

    # 初期化
    for i in range(N):
        d[i][i] = 0
        nr[i][i] = (0, L)

    for a, b, c in abc_list:
        if c > L:
            # そもそも燃料が足りず通れないことがある
            pass
        else:
            d[a][b] = c
            d[b][a] = c

            nr[a][b] = (0, L-c)
            nr[b][a] = (0, L-c)

    # 最短経路
    d = warshall_floyd(d)
    # 回数
    nr = nr_warshall_floyd(nr, d, L)
    dprint(d)
    dprint(nr)
    for s, t in q_list:
        ans = nr[s][t][0]
        if ans == nmx:
            print(-1)
        else:
            print(ans)

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] = 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
from collections import defaultdict

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N, M, L = map(int, input().split())
        ABC = [list(map(int, input().split())) for _ in range(M)]
        Q = int(input())
        st = [list(map(int, input().split())) for _ in range(Q)]

        load1 = defaultdict(lambda: None)
        load2 = defaultdict(lambda: None)

        for abc in ABC:
            load1[abc[0]] = (abc[1], abc[2])
            load2[abc[1]] = (abc[0], abc[2])

        for _st in st:
            ans = 0
            start, goal = _st[0], _st[1]
            if start == goal:
                continue

            elif start < goal:
                l = L
                f = True
                while start != goal:
                    tmp = load1[start]
                    if not tmp:
                        f = False
                        break
                    start = tmp[0]
                    l -= tmp[1]
                    if l < 0:
                        l += L
                        ans += 1
                    if l < 0:
                        f = False
                        break
                if f:
                    print(ans)
                else:
                    print(-1)
            else:
                l = L
                f = True
                while start != goal:
                    tmp = load2[start]
                    if not tmp:
                        f = False
                        break
                    start = tmp[0]
                    l -= tmp[1]
                    if l < 0:
                        l += L
                        ans += 1
                    if l < 0:
                        f = False
                        break
                if f:
                    print(ans)
                else:
                    print(-1)


# Run main
if __name__ == '__main__':
    AtCoder().main()

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import shortest_path,floyd_warshall
from scipy.sparse import csr_matrix

def get_path(start, goal, pred):
  return get_path_row(start, goal, pred[start])

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

N,M,L = map(int,input().split())
if M != 0:
  G = [[0 for _ in range(N)] for _ in range(N)]
  for i in range(M):
    A,B,C = map(int,input().split())
    A -= 1
    B -= 1
    if C <= L:
      G[A][B] = C
      G[B][A] = C
  csr = csr_matrix(G)
  #print(csr)
  #d, p = shortest_path(csr, return_predecessors=True)
  d, p = floyd_warshall(csr, return_predecessors=True)
  #print(d)
  #print(p)

Q = int(input())
for i in range(Q):
  if M == 0:
    print(-1)
    break
  s,t = map(int,input().split())
  s -= 1
  t -= 1
  path = get_path(s,t,p)
  if len(path) == 0:
    print(-1)
  else:
    ans = 0
    tank = L
    for j in range(len(path)-1):
      if tank - G[path[j]][path[j+1]] < 0:
        ans +=1
        tank = L
      tank -= G[path[j]][path[j+1]]
    print(ans)

Submission status: Wrong Answer

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