Submission #1553117

---

Source Code Expand

temp = input().split(" ")
n_town = int(temp[0])
n_load = int(temp[1])

temp = input().split(" ")
start = int(temp[0])
goal = int(temp[1])


OOKII = 10000000
distance = [OOKII for i in range(n_town+1)]
distance[start] = 0
map = [[OOKII for i in range(n_town+1)] for j in range(n_town+1)]


for a in range(n_load):
    temp = input().split(" ")
    frm = int(temp[0])
    to = int(temp[1])
    cost = int(temp[2])
    map[frm][to] = cost
    map[to][frm] = cost

while 1:
    update = 0
    for a in range(n_town+1):
        for b in range(n_town+1):
            if(distance[a] != OOKII and distance[b] > distance[a] + map[a][b]):
                distance[b] = distance[a] + map[a][b]
                print("a:",a,"b:",b)
                print("cost:",map[a][b])
                print("dist[a]",distance[a],"new dist[b]",distance[b])
                update = 1
    if(update == 0):
        break
    
print(map)
print(distance)

atta = 0
for mid in range(n_town):
    mid = mid+1
    distance2 = [OOKII for i in range(n_town+1)]
    distance2[mid] = 0
    while 1:
        update = 0
        for a in range(n_town+1):
            for b in range(n_town+1):
                if(distance2[a] != OOKII and distance2[b] > distance2[a] + map[a][b]):
                    distance2[b] = distance2[a] + map[a][b]
                    update = 1
        if(update == 0):
            break
    if(distance[mid] ==distance2[goal]):
        print(mid)
        break
if(atta = 0):
    print("-1")

Submission Info

Judge Result