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:
n,m,l=map(int,input().split())
cost=[[10**9+1]*n for i in range(n)]
length=[[(10**9,-l)]*n for i in range(n)]
for i in range(m):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    cost[a][b]=c
    cost[b][a]=c
for i in range(n):
    length[i][i]=(0,-l)
q=int(input())
st=[map(int,input().split())for i in range(q)]

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

g=[[]for i in range(n)]
for i in range(m):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    g[a].append((b,c))
    g[b].append((a,c))
q=int(input())
st=[list(map(int,input().split())) for i in range(q)]

import heapq

totoalcost=[[10**18]*n for i in range(n)]

#ダイクストラ
for i in range(n):
    check=0
    hq=[(0,-l,i)]#change times,-oil,point
    while check!=((1<<n)-1):
        if not hq:
            break
        nowch,oil,now=heapq.heappop(hq)
        if check&(1<<now):
            break
        check|=(1<<now)
        totoalcost[i][now]=min(totoalcost[i][now],nowch)

        oil*=-1
        for to,cost in g[now]:
            if check&1<<to or cost>l:
                continue
            elif cost<=oil:
                heapq.heappush(hq,(nowch,-(oil-cost),to))
            else:
                heapq.heappush(hq,(nowch+1,-(l-cost),to))

for s,t in st:
    i=totoalcost[s-1][t-1]
    if i>10**16:
        print(-1)
    else:
        print(i)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,M,L = map(int,readline().split())
ABC = [list(map(int,readline().split())) for _ in range(M)]
Q = int(readline())
ST = [list(map(int,readline().split())) for _ in range(Q)]
    
def warshall_floyd(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

INF = 10**5
d = [[INF]*N for i in range(N)] 
a =  [[INF]*N for i in range(N)] 
for x,y,z in ABC:
    if z <= L:
      d[x-1][y-1] = z
      d[y-1][x-1] = z
for i in range(N):
    d[i][i] = 0
    a[i][i] = 1
chk = warshall_floyd(d)

for i in range(N-1):
  for j in range(i+1,N):
    if chk[i][j] <= L:
      a[i][j] = 1
      a[j][i] = 1
ans = warshall_floyd(a)

for s,t in ST:
  answer = ans[s-1][t-1]
  if answer == INF:
      print(-1)
  else:
      print(answer-1)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,M,L = map(int,readline().split())
ABC = [list(map(int,readline().split())) for _ in range(M)]
Q = int(readline())
ST = [list(map(int,readline().split())) for _ in range(Q)]
    
def warshall_floyd(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

INF = 10**5
d = [[INF]*N for i in range(N)] 
a =  [[INF]*N for i in range(N)] 
for x,y,z in ABC:
    if z <= L:
      d[x-1][y-1] = z
      d[y-1][x-1] = z
for i in range(N):
    d[i][i] = 0
    a[i][i] = 0
chk = warshall_floyd(d)

for i in range(N-1):
  for j in range(i+1,N):
    if chk[i][j] <= L:
      a[i][j] = 1
      a[j][i] = 1
ans = warshall_floyd(a)

for s,t in ST:
  answer = ans[s-1][t-1]
  if answer == INF:
      print(-1)
  else:
      print(answer-1)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,M,L = map(int,readline().split())
ABC = [list(map(int,readline().split())) for _ in range(M)]
Q = int(readline())
ST = [list(map(int,readline().split())) for _ in range(Q)]
    
def warshall_floyd(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

INF = 10**5
d = [[INF]*N for i in range(N)] 
for x,y,z in ABC:
    if z <= L:
      d[x-1][y-1] = z
      d[y-1][x-1] = z
for i in range(N):
    d[i][i] = 0
chk = warshall_floyd(d)

for s,t in ST:
  answer = chk[s-1][t-1]
  if answer == INF:
      print(-1)
  else:
      print((answer-1)//L)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from heapq import heappush, heappop

N,M,L = map(int,readline().split())
ABC = [list(map(int,readline().split())) for _ in range(M)]
Q = int(readline())
ST = [list(map(int,readline().split())) for _ in range(Q)]

graph = [[] for _ in range(N)]
for a,b,c in ABC:
  if c <= L:
    graph[a-1].append((b-1,c))
    graph[b-1].append((a-1,c))

def f(s,g):
  dist = [INF] * N
  used = [True] * N #True:未確定
  dist[s] = 0
  q = [(0,0,s,L)] # 総距離、補給回数、行先、残量

  while q:
      dd,cnt,v,za = heappop(q)
      if v == g:
          break
      if not used[v]:
          continue
      used[v] = False
      if dist[v] < cnt:
          continue
      
      # 移動
      for w,cost in graph[v]: # 行先、消費
        if cost <= za:
          if dist[w] <= cnt:
              continue
          dist[w] = cnt
          heappush(q,(dd+cost,cnt,w,za-cost))
        else:
          if dist[w] <= cnt+1:
              continue
          dist[w] = cnt+1
          heappush(q,(dd+cost,cnt+1,w,L-cost))
          
  return dist[g]

INF = 10**5
for i in range(Q):
  answer = f(ST[i][0]-1,ST[i][1]-1)
  if answer == INF:
      answer = -1
  print(answer)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from heapq import heappush, heappop

N,M,L = map(int,readline().split())
ABC = [list(map(int,readline().split())) for _ in range(M)]
Q = int(readline())
ST = [list(map(int,readline().split())) for _ in range(Q)]

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

def f(s,g):
  dist = [INF] * N
  dist[s] = 0
  q = [(0,s,L)] # 補給回数、行先、残量

  while q:
      cnt,v,za = heappop(q)
      if dist[v] < cnt:
          continue
      if v == g:
          break
      
      # 移動
      for w,cost in graph[v]: # 行先、消費
        if cost <= za:
          if dist[w] <= cnt:
              continue
          dist[w] = cnt
          heappush(q,(cnt,w,za-cost))
        else:
          if dist[w] <= cnt+1:
              continue
          if L < cost:
              continue
          dist[w] = cnt+1
          heappush(q,(cnt+1,w,L-cost))
          
  return dist[g]

INF = 10**5
for i in range(Q):
  answer = f(ST[i][0]-1,ST[i][1]-1)
  if answer == INF:
      answer = -1
  print(answer)

Submission status: Wrong Answer

Solution code:
import heapq
import sys
def main():
    input=sys.stdin.readline
    n,m,l=map(int,input().split())
    edge=[[] for i in range(n)]
    for _ in range(m):
        a,b,c=map(int,input().split())
        if c>l:
            continue
        a-=1
        b-=1
        edge[a].append((c,b))
        edge[b].append((c,a))
    def dijkstra(s):
        used=[[True] for _ in range(n)]
        dist=[[10**18,10**18] for _ in range(n)]
        q=[]
        heapq.heappush(q,((0,0),s))
        while q:
            p,x=heapq.heappop(q)
            time,cons=p
            dist[x]=[time,cons]
            used[x]=False
            for cost,nx in edge[x]:
                if  not used[nx]:
                    continue
                ntime,ncons=dist[nx]
                if l-cons>=cost:
                    if ntime>time:
                        dist[nx]=[time,cons+cost]
                        heapq.heappush(q,((time,cons+cost),nx))
                    elif ntime==time:
                        if ncons>cons+cost:
                            dist[nx]=[time,cons+cost]
                            heapq.heappush(q,((time,cons+cost),nx))
                else:
                    if ntime>time+1:
                        dist[nx]=[time+1,cost]
                        heapq.heappush(q,((time+1,cost),nx))
                    elif ntime==time+1:
                        if ncons>cost:
                            dist[nx]=[ntime,cost]
                            heapq.heappush(q,((ntime,cost),nx))
        return dist
    ans=[]
    for i in range(n):
        ans.append(dijkstra(i))
    q=int(input())
    for _ in range(q):
        s,t=map(int,input().split())
        s-=1
        t-=1
        if ans[s][t][0]==10**18:
            print(-1)
        else:
            print(ans[s][t][0])
if __name__=="__main__":
  main()

Submission status: Wrong Answer

Solution code:
import heapq
import sys
def main():
    input=sys.stdin.readline
    n,m,l=map(int,input().split())
    edge=[[] for i in range(n)]
    for _ in range(m):
        a,b,c=map(int,input().split())
        if c>l:
            continue
        a-=1
        b-=1
        edge[a].append((c,b))
        edge[b].append((c,a))
    def dijkstra(s):
        used=[[True] for _ in range(n)]
        dist=[[10**18,10**18] for _ in range(n)]
        q=[]
        heapq.heappush(q,(0,0,s))
        while q:
            time,cons,x,=heapq.heappop(q)
            dist[x]=[time,cons]
            used[x]=False
            for cost,nx in edge[x]:
                if  not used[nx]:
                    continue
                ntime,ncons=dist[nx]
                if l-cons>=cost:
                    if ntime>time:
                        dist[nx]=[time,cons+cost]
                        heapq.heappush(q,(time,cons+cost,nx))
                    elif ntime==time:
                        if ncons>cons+cost:
                            dist[nx]=[time,cons+cost]
                            heapq.heappush(q,(time,cons+cost,nx))
                else:
                    if ntime>time+1:
                        dist[nx]=[time+1,cost]
                        heapq.heappush(q,(time+1,cost,nx))
                    elif ntime==time+1:
                        if ncons>cost:
                            dist[nx]=[ntime,cost]
                            heapq.heappush(q,(ntime,cost,nx))
        return dist
    ans=[]
    for i in range(n):
        ans.append(dijkstra(i))
    #print(dijkstra(6))
    q=int(input())
    for _ in range(q):
        s,t=map(int,input().split())
        s-=1
        t-=1
        if ans[s][t][0]==10**18:
            print(-1)
        else:
            print(ans[s][t][0])
if __name__=="__main__":
  main()

Submission status: Wrong Answer

Solution code:
import heapq
import sys
def main():
    input=sys.stdin.readline
    n,m,l=map(int,input().split())
    edge=[[] for i in range(n)]
    for _ in range(m):
        a,b,c=map(int,input().split())
        a-=1
        b-=1
        edge[a].append((c,b))
        edge[b].append((c,a))
    def dijkstra(s):
        used=[[True] for _ in range(n)]
        dist=[[10**18,10**18] for _ in range(n)]
        q=[]
        heapq.heappush(q,(0,0,s))
        while q:
            time,cons,x,=heapq.heappop(q)
            dist[x]=[time,cons]
            used[x]=False
            for cost,nx in edge[x]:
                if  not used[nx]:
                    continue
                ntime,ncons=dist[nx]
                if l-cons>=cost:
                    if ntime>time:
                        dist[nx]=[time,cons+cost]
                        heapq.heappush(q,(time,cons+cost,nx))
                    elif ntime==time:
                        if ncons>cons+cost:
                            dist[nx]=[time,cons+cost]
                            heapq.heappush(q,(time,cons+cost,nx))
                else:
                    if ntime>time+1:
                        dist[nx]=[time+1,cost]
                        heapq.heappush(q,(time+1,cost,nx))
                    elif ntime==time+1:
                        if ncons>cost:
                            dist[nx]=[ntime,cost]
                            heapq.heappush(q,(ntime,cost,nx))
        return dist
    ans=[]
    for i in range(n):
        ans.append(dijkstra(i))
    q=int(input())
    for _ in range(q):
        s,t=map(int,input().split())
        s-=1
        t-=1
        if ans[s][t][0]==10**18:
            print(-1)
        else:
            print(ans[s][t][0])
if __name__=="__main__":
  main()

Submission status: Wrong Answer

Solution code:
import heapq
import sys
def main():
    input=sys.stdin.readline
    n,m,l=map(int,input().split())
    edge=[[[] for _ in range(2)] for i in range(n)]
    for _ in range(m):
        a,b,c=map(int,input().split())
        a-=1
        b-=1
        edge[a][1].append((0,c,b,0))
        edge[a][0].append((0,c,b,0))
        edge[a][0].append((1,0,a,1))
        edge[b][1].append((0,c,a,0))
        edge[b][0].append((0,c,a,0))
        edge[b][0].append((1,0,b,1))
    def dijkstra(s):
        used=[[True]*2 for _ in range(n)]
        dist=[[10**18]*2 for _ in range(n)]
        q=[]
        heapq.heappush(q,(0,l,s,1))
        while q:
            d,f,x,flg=heapq.heappop(q)
            dist[x][flg]=d
            used[x][flg]=False
            for nd,nf,nx,nflg in edge[x][flg]:
                if  not used[nx][nflg]:
                    continue
                if flg==0:
                    if nflg==0:
                        if f>=nf:
                            if dist[nx][nflg]>dist[x][flg]:
                                dist[nx][nflg]=dist[x][flg]
                                heapq.heappush(q,(dist[nx][nflg],f-nf,nx,nflg))
                    else:
                        if l>=nf:
                            if dist[nx][nflg]>dist[x][flg]+1:
                                dist[nx][nflg]=dist[x][flg]+1
                                heapq.heappush(q,(dist[nx][nflg],l-nf,nx,nflg))
                else:
                    if f>=nf:
                        if dist[nx][nflg]>dist[x][flg]:
                            dist[nx][nflg]=dist[x][flg]
                            heapq.heappush(q,(dist[nx][nflg],f-nf,nx,nflg))
        return dist
    ans=[]
    for i in range(n):
        ans.append(dijkstra(i))
    q=int(input())
    for _ in range(q):
        s,t=map(int,input().split())
        s-=1
        t-=1
        if min(ans[s][t])==10**18:
            print(-1)
        else:
            print(min(ans[s][t]))
if __name__=="__main__":
  main()

Submission status: Wrong Answer

Solution code:
import heapq
import sys
def main():
    input=sys.sydin.readline
    n,m,l=map(int,input().split())
    edge=[[[] for _ in range(2)] for i in range(n)]
    for _ in range(m):
        a,b,c=map(int,input().split())
        a-=1
        b-=1
        edge[a][1].append((0,c,b,0))
        edge[a][0].append((0,c,b,0))
        edge[a][0].append((1,0,a,1))
        edge[b][1].append((0,c,a,0))
        edge[b][0].append((0,c,a,0))
        edge[b][0].append((1,0,b,1))
    def dijkstra(s):
        used=[[True]*2 for _ in range(n)]
        dist=[[10**18]*2 for _ in range(n)]
        q=[]
        heapq.heappush(q,(0,l,s,1))
        while q:
            d,f,x,flg=heapq.heappop(q)
            dist[x][flg]=d
            used[x][flg]=False
            for nd,nf,nx,nflg in edge[x][flg]:
                if  not used[nx][nflg]:
                    continue
                if flg==0:
                    if nflg==0:
                        if f>=nf:
                            if dist[nx][nflg]>dist[x][flg]:
                                dist[nx][nflg]=dist[x][flg]
                                heapq.heappush(q,(dist[nx][nflg],f-nf,nx,nflg))
                    else:
                        if l>=nf:
                            if dist[nx][nflg]>dist[x][flg]+1:
                                dist[nx][nflg]=dist[x][flg]+1
                                heapq.heappush(q,(dist[nx][nflg],l-nf,nx,nflg))
                else:
                    if f>=nf:
                        if dist[nx][nflg]>dist[x][flg]:
                            dist[nx][nflg]=dist[x][flg]
                            heapq.heappush(q,(dist[nx][nflg],f-nf,nx,nflg))
        return dist
    ans=[]
    for i in range(n):
        ans.append(dijkstra(i))
    q=int(input())
    for _ in range(q):
        s,t=map(int,input().split())
        s-=1
        t-=1
        if min(ans[s][t])==10**18:
            print(-1)
        else:
            print(min(ans[s][t]))

Submission status: Wrong Answer

Solution code:
import heapq
n,m,l=map(int,input().split())
edge=[[[] for _ in range(2)] for i in range(n)]
for _ in range(m):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    edge[a][1].append((0,c,b,0))
    edge[a][0].append((0,c,b,0))
    edge[a][0].append((1,0,a,1))
    edge[b][1].append((0,c,a,0))
    edge[b][0].append((0,c,a,0))
    edge[b][0].append((1,0,b,1))
def dijkstra(s):
    used=[[True]*2 for _ in range(n)]
    dist=[[10**18]*2 for _ in range(n)]
    q=[]
    heapq.heappush(q,(0,l,s,1))
    while q:
        d,f,x,flg=heapq.heappop(q)
        dist[x][flg]=d
        used[x][flg]=False
        for nd,nf,nx,nflg in edge[x][flg]:
            if  not used[nx][nflg]:
                continue
            if flg==0:
                if nflg==0:
                    if f>=nf:
                        if dist[nx][nflg]>dist[x][flg]:
                            dist[nx][nflg]=dist[x][flg]
                            heapq.heappush(q,(dist[nx][nflg],f-nf,nx,nflg))
                else:
                    if l>=nf:
                        if dist[nx][nflg]>dist[x][flg]+1:
                            dist[nx][nflg]=dist[x][flg]+1
                            heapq.heappush(q,(dist[nx][nflg],l-nf,nx,nflg))
            else:
                if f>=nf:
                    if dist[nx][nflg]>dist[x][flg]:
                        dist[nx][nflg]=dist[x][flg]
                        heapq.heappush(q,(dist[nx][nflg],f-nf,nx,nflg))
    return dist
ans=[]
for i in range(n):
  ans.append(dijkstra(i))
q=int(input())
for _ in range(q):
  s,t=map(int,input().split())
  s-=1
  t-=1
  if min(ans[s][t])==10**18:
      print(-1)
  else:
      print(min(ans[s][t]))

Submission status: Wrong Answer

Solution code:
import heapq
def dijkstra_heap(s,g):
    #始点sから各頂点への最短距離
    global L,n
    d = [n] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    ed_list = []
    for es in edge[s]:
        heapq.heappush(ed_list,(es[0],es[1],L,0,es[0])) 
        #累計消費、行先、残量、給油回数、今回の消費
    while len(ed_list):
        A,B,C,D,E = heapq.heappop(ed_list)
        if E > C:
          z = L-E; c = 1
          if z < 0:
              break
        else:
          z = C-E; c = 0
        if not used[B]:
            continue
        v = B
        d[v] = D+c
        used[v] = False
        if v == g:
          break
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(ed_list,(e[0]+A,e[1],z,D+c,e[0]))
                  
    return d[g]

import sys
input = sys.stdin.readline
n,m,L = map(int,input().split()) #n:頂点数　w:辺の数

edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(m):
    x,y,z = map(int,input().split())
    edge[x-1].append((z,y-1)) # list限定
    edge[y-1].append((z,x-1))
q = int(input())
for i in range(q):
  s,t = map(int,input().split())
  ans = dijkstra_heap(s-1,t-1)
  if ans == n:
    print(-1)
  else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
def dijkstra_heap(s,g):
    #始点sから各頂点への最短距離
    global L,n
    d = [n] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    ed_list = []
    for es in edge[s]:
        heapq.heappush(ed_list,[es[0],es[1],L,0,es[0]]) 
        #累計消費、行先、残量、給油回数、今回の消費
    while len(ed_list):
        poped = heapq.heappop(ed_list)
        if poped[4] > poped[2]:
          z = L-(poped[4]); c = 1
          if z < 0:
              break
        else:
          z = poped[2]-poped[4]; c = 0
        if not used[poped[1]]:
            continue
        v = poped[1]
        d[v] = poped[3]+c
        used[v] = False
        if v == g:
          break
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(ed_list,[e[0]+poped[0],e[1],z,poped[3]+c,e[0]])
                  
    return d[g]

import sys
input = sys.stdin.readline
n,m,L = map(int,input().split()) #n:頂点数　w:辺の数

edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(m):
    x,y,z = map(int,input().split())
    edge[x-1].append([z,y-1]) # list限定
    edge[y-1].append([z,x-1])
q = int(input())
for i in range(q):
  s,t = map(int,input().split())
  ans = dijkstra_heap(s-1,t-1)
  if ans == n:
    print(-1)
  else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
def dijkstra_heap(s,g):
    #始点sから各頂点への最短距離
    global L,n
    d = [float('inf')] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    ed_list = []
    for es in edge[s]:
        heapq.heappush(ed_list,[es[0],es[1],L,0]) #消費、行先、残量、給油回数
    while len(ed_list):
        poped = heapq.heappop(ed_list)
        if poped[0] > poped[2]:
          z = L-poped[0]; c = 1
          if poped[0] > L:
              break
        else:
          z = poped[2]-poped[0]; c = 0
        if not used[poped[1]]:
            continue
        v = poped[1]
        d[v] = poped[3]+c
        used[v] = False
        if v == g:
          break
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(ed_list,[e[0],e[1],z,poped[3]+c])
                  
    return d[g]

import sys
input = sys.stdin.readline
n,m,L = map(int,input().split()) #n:頂点数　w:辺の数

edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(m):
    x,y,z = map(int,input().split())
    edge[x-1].append([z,y-1]) # list限定
    edge[y-1].append([z,x-1])
q = int(input())
for i in range(q):
  s,t = map(int,input().split())
  ans = dijkstra_heap(s-1,t-1)
  if ans == float('inf'):
    print(-1)
  else:
    print(ans)

Submission status: Wrong Answer

Solution code:
#全点対間最短経路を求めるアルゴリズム

def warshall_floyd(d):
    #d[i][j]:iからjに行く最短経路
    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])
    return d

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**9)

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

INF = 10 ** 11
d = [[INF]*(n+1) for _ in range(n+1)]
for i in range(m):
        x, y, z = map(int, input().split())
        if z <= l:
            d[x][y] = z
            d[y][x] = z #無向グラフならつける

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

    

ss = warshall_floyd(d)



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


#補給回数
vv = warshall_floyd(ss)

for i in range(1,n+1):
    for j in range(1,n+1):
        if vv[i][j] == INF:
            vv[i][j] = -1

q = int(input())
for _ in range(q):
    x, y = map(int, input().split())
    print(vv[x][y]-1)

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.buffer.readline

n, m, limit = map(int, input().split())
infi = 10 ** 15
graph = [[infi] * (n + 1) for _ in range(n + 1)]
step = [[infi] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a][b] = c
    graph[b][a] = c
for k in range(1, n + 1):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            graph[i][j] = min(graph[i][k] + graph[k][j], graph[i][j])
for i in range(1, n + 1):
    for j in range(1, n + 1):
        if graph[i][j] <= limit:
            graph[i][j] = 1
        elif graph[i][j] == 0:
            graph[i][j] = 0
        else:
            graph[i][j] = infi
for k in range(1, n + 1):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            graph[i][j] = min(graph[i][k] + graph[k][j], graph[i][j])


q = int(input())
for _ in range(q):
    a, b = map(int, input().split())
    if graph[a][b] == infi:
        graph[a][b] = 0
    print(graph[a][b] - 1 if graph[i][j] != infi else -1)

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.buffer.readline

n, m, limit = map(int, input().split())
infi = 10 ** 15
graph = [[infi] * (n + 1) for _ in range(n + 1)]
step = [[infi] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a][b] = c
    graph[b][a] = c
for k in range(1, n + 1):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            graph[i][j] = min(graph[i][k] + graph[k][j], graph[i][j])
for i in range(1, n + 1):
    for j in range(1, n + 1):
        if graph[i][j] <= limit:
            graph[i][j] = 1
        else:
            graph[i][j] = infi
for k in range(1, n + 1):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            graph[i][j] = min(graph[i][k] + graph[k][j], graph[i][j])


q = int(input())
for _ in range(q):
    a, b = map(int, input().split())
    if graph[a][b] == infi:
        graph[a][b] = 0
    print(graph[a][b] - 1 if graph[i][j] != infi else -1)