[伯俊]1238パーティー

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

質問する

N個の数字で区切られた村ごとに学生が住んでいる.
ある日、このN人の学生はX(1≦X≦N)号村でパーティーをすることにした.この村の間にはM本の一方向道路があり、i号道路を通ってti(1≦ti≦100)の時間を費やしている.
学生はみな歩いて村に帰ってパーティーに参加しなければならない.しかし、これらの学生はもともと怠け者で、最短時間で行き来したいと思っています.
これらの道は一方的で、彼らが行く道が違うかもしれません.N人の学生の中で最も多くの時間を費やした学生を探し出す.

入力

1行目はN(1≦N≦1000)、M(1≦M≦10000)と入力し、Xはスペースに区切られる.2列目からM+1列、i号道路の起点、終点、そしてこの道路を通過するのに要する時間は、いずれもTiに入る.始点と終点が同じ道路はなく、始点と一つの都市Aから別の都市Bまでの道路は最大1本である.
すべての学生は家からXに行くことができて、Xから家に帰ることができるデータだけを入力します.

しゅつりょく

1行目は、N名の学生の中で最も長い時間往復する学生の所要時間を印刷する.

コミットコード

import sys
import heapq
input = sys.stdin.readline

n, m, x = map(int, input().split())
graph = [[] for _ in range(n + 1)]
answer = [0] * (n + 1)
INF = int(1e9)
distance = [[INF] * (n + 1) for _ in range(n + 1)]

for i in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))

for i in range(1, n + 1):
    q = []
  
    # start node i
    distance[i][i] = 0
  
    heapq.heappush(q, (0, i))
    while q:
        dist, now = heapq.heappop(q)
        if distance[i][now] < dist: continue
      
        for g in graph[now]:
            if distance[i][g[0]] > dist + g[1]:
                distance[i][g[0]] = distance[i][now] + g[1]
                heapq.heappush(q, (distance[i][g[0]], g[0]))


for i in range(1, n + 1):
    answer[i] += distance[i][x] + distance[x][i]

print(max(answer))

これは多項式最短距離アルゴリズムPythonの基本例では何の応用もない問題である.
エストラのアルゴリズムを勉強したばかりの人なら、練習問題として解くことができます.