알고리즘_최단거리_플로이드 워셜

노드 사이 최단 거리를 구하되 다양한 경로를 모두 고려하여 최단거리를 2차원 배열 그래프에 저장한다.

단 이때 프롤이드 워셜은 중간에 거쳐갈 노드를 for 문으로 돌면서 비교해본다. 그냥 바로 노드를 갔을때랑 중간 노드를 거쳐서 갔을 경우 거리를 비교하여 최소 값을 저장하여 노드를 순환하게 되는 오류도 제거할 수 있다.

INF = int(200)
n, m, r = map(int,input().split())
graph = [[INF] * (n + 1) for _ in range(n+1)]
items = list(map(int,input().split()))
answer = []

# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for a in range(1,n+1):
    graph[a][a] = 0

# 각 간선에 대한 정보를 입력받아, 그 값으로 초기화
for _ in range(r):
    s, e, d = map(int,input().split())
    graph[s][e] = d
    graph[e][s] = d  #노드 이동 방향이 없어서 추가해줌
    # 만약 방향이 있는 거리 정보라면 위에 하나만 적어준다.

# 점화식에 따라 플로이드 워셜 알고리즘 수행
for k in range(1,n+1):
    for a in range(1,n+1):
        for b in range(1,n+1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

# 시작 노드별 최대 파밍 저장
for start_node in range(1,n+1):
    pharming = 0
    for i in range(1,n+1):
        distance = graph[start_node][i]
        if distance <= m:
            pharming += items[i-1]
    answer.append(pharming)
print(max(answer))

[[200, 200, 200, 200, 200, 200],
 [200, 200, 200, 200, 200, 200],
 [200, 200, 200, 200, 200, 200],
 [200, 200, 200, 200, 200, 200],
 [200, 200, 200, 200, 200, 200],
 [200, 200, 200, 200, 200, 200]]

[[200, 200, 200, 200, 200, 200],
 [200, 0, 3, 6, 5, 7],
 [200, 3, 0, 3, 8, 4],
 [200, 6, 3, 0, 11, 7],
 [200, 5, 8, 11, 0, 12],
 [200, 7, 4, 7, 12, 0]]

0 3 6 5 7 
3 0 3 8 4 
6 3 0 11 7 
5 8 11 0 12 
7 4 7 12 0