백준 14938번 서강그라운드

https://www.acmicpc.net/problem/14938

14938번: 서강그라운드

vertex와 edge의 최대개수가 100개 밖에 되지 않아서 각 vertex에서 시작하는 모든 경우의 수를 브루트 포스로 계산해 주어도 시간초과가 나지 않는 문제이다.

플로이드 와셜과 다익스트라 두개의 방법으로 해결할 수 있다.

#dijkstra
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

n,m,r = map(int,input().split())
items = list(map(int,input().split()))

graph = [[] for i in range(n + 1)]

for _ in range(r):
    a,b,c = map(int,input().split())

    graph[a].append((b,c))
    graph[b].append((a,c))

def dijkstra(start):
    q = []
    heapq.heappush(q,(0,start))
    distance[start] = 0

    while q:
        dist, now = heapq.heappop(q)

        if distance[now] < dist:
            continue

        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q,(cost,i[0]))

total_result = []
for i in range(1,n+1):
    distance = [INF] * (n + 1)
    dijkstra(i)

    idx_list = []
    for idx, each in enumerate(distance):
        if each <= m:
            idx_list.append(idx)

    tmp = []
    for each in idx_list:
        tmp.append(items[each - 1])

    total_result.append(sum(tmp))

print(max(total_result))

#floyd warshall
import sys

input = sys.stdin.readline
INF = int(1e9)

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

for a in range(1, n + 1):
    for b in range(1, n + 1):
        if a == b:
            graph[a][b] = 0

for _ in range(r):
    s, e, c = map(int, input().split())
    if graph[s][e] > c:
        graph[s][e] = c

    if graph[e][s] > c:
        graph[e][s] = c

for k in range(1, n + 1):
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            if a == b:
                graph[a][b] = 0
            else:
                graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

total_result = []
for vertex in graph[1:]:

    idx_list = []
    for idx, each in enumerate(vertex[1:]):
        if each <= m:
            idx_list.append(idx)

    tmp = []
    for each in idx_list:
        tmp.append(items[each])

    total_result.append(sum(tmp))

print(max(total_result))