[python]伯俊11265終わらないパーティー(Floyd-Warshall)

📌 質問する

パーティー好きのミンホは、パーティーが続く遊園地「ミンホワールド」を作った.最初はパーティー会場が1つしかない小さな遊園地だったが、ますます多くの人がパーティー会場を拡張し、現在はNつのパーティー会場を持つ大きな遊園地となっている.民浩はパーティー会場を拡張するたびに、便宜上、新しいパーティー会場と既存のすべてのパーティー会場を直接接続できる道路を建設する.このとき建設された道路は利用者を便利にするために一方通行に設計されている.
キャプテンが少ない時は悪くなかったが、キャプテンが多くなり、現在は以下の2つの問題が発生している.

Aパーティー場からBパーティー場に素早く到着するために、直接接続された片道が設けられていますが、AやBではなく他のパーティー場を通って早く到着する可能性もあります.

今からCまでの時間の後、B番パーティー場で新しいパーティーが開かれますが、1番と同じ理由で、今のAパーティー場からB番パーティー場までパーティーの時間に間に合うかどうか分かりにくいです.

これらの問題で観光客の不満が高まり、民浩はこの問題を解決するために高速ナビゲーションサービスを実施することにしたが、サービス要求が多すぎて業務が麻痺した.そこで民浩はあなたのこの天才プログラマーにこの問題を解決するように頼んだ.民浩を助けてプログラムを作って、あるパーティー場から別のパーティー場に行って、時間内に到着できるかどうかを見てみましょう.

入力

入力された最初の行は、キャプテンのサイズN(5≦N≦500)と、サービスを要求する顧客の数M(1≦M≦10000)を与える.各宴会場には1番からN番まで番号がついています.次はN行で、各行にはN個の数があります.i列のj回数T(1≦T≦1000000)とは、i列から直接j列に接続された道路を移動する時間を指す.
次のM行は3つの整数A,B,Cを与える.A(1≦A≦N)は招待サービスの客がいる宴会場番号、B(1≦B≦N)は次の宴会場番号、C(1≦C≦10000000)はこれから次の宴会を開くのに要する時間を示す.

しゅつりょく

M行にまたがるサービスを要請した客が時間内に別の宴会場に到着できる場合は「Enjoy other party」を出力し、時間内に到着できない場合は「Stay here」を出力する.

入力例1

5 10
0 4 4 8 7
7 0 7 7 4
1 4 0 5 4
5 2 2 0 7
1 4 1 6 0
1 3 8
2 4 1
4 1 1
1 5 5
3 2 1
3 2 5
4 5 10
5 3 2
1 4 1
1 4 11

サンプル出力1

Enjoy other party
Stay here
Stay here
Stay here
Stay here
Enjoy other party
Enjoy other party
Enjoy other party
Stay here
Enjoy other party

📌 に答える

💬 Code

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]

for k in range(n):
    for i in range(n):
        for j in range(n):
            if graph[i][j] > graph[i][k] + graph[k][j]:
                graph[i][j] = graph[i][k] + graph[k][j]

for _ in range(m):
    a, b, time = map(int, input().split())
    if graph[a-1][b-1] <= time:
        print('Enjoy other party')
    else:
        print('Stay here')

💡 Solution

A 파티장에서 B 파티장으로 빨리 갈 수 있도록
직접 연결이 된 일방통행 도로를 만들었지만
A와 B가 아닌 다른 파티장을 경유해서
더 빨리 갈 수 있는 경우가 있을 수 있다.

上記の条件により,この問題は最短経路問題に相当し,すべてのノードの最短経路を計算する必要があるためfloydwalshアルゴリズムを採用した.

for k in range(n):
    for i in range(n):
        for j in range(n):
            if graph[i][j] > graph[i][k] + graph[k][j]:
                graph[i][j] = graph[i][k] + graph[k][j]

iパーティー場からjパーティー場に向かう場合、kパーティー場を経由する方が早いと最短経路で更新できます.

for _ in range(m):
    a, b, time = map(int, input().split())
    if graph[a-1][b-1] <= time:
        print('Enjoy other party')
    else:
        print('Stay here')

問題ではキャプテンの番号を1からnと指定しているので、図にアクセスする際にはインデックスから1を減算した場合にアクセスする必要があります.

🤔 タイムアウトの問題

最高値をminに更新

for k in range(n):
    for i in range(n):
        for j in range(n):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

ifゲートで最高値を更新

for k in range(n):
    for i in range(n):
        for j in range(n):
            if graph[i][j] > graph[i][k] + graph[k][j]:
                graph[i][j] = graph[i][k] + graph[k][j]

min()を使用すると、graph[i][j]、graph[i][k]+graph[k][j]を毎回比較し、graph[i][j]の操作に割り当てる.したがってgraph[i][j]をgraph[i][j]に割り当てることが頻繁に発生する.
逆に、文が条件を満たしていない場合は、文は割り当てられないため、不要な割り当て操作は発生しません.

for i in range(n) ❌

for i in range(m):
    a, b, time = map(int, input().split())

for _ in range(n) ⭕

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

for文では,変数iを用いることがなければ,変数を指定しない習慣を身につける.これがタイムアウトになるとは思わなかったのですが・・・
pypy 3で採点すれば両方とも❌で採点してもタイムアウト判定なしで正解が得られますが、pyth 3で採点すれば両方とも❌で採点して正解が得られます.
floydwalshアルゴリズムはノードが500個未満の場合に適しているが,この問題では最大500個のノードがあり,時間がかなり短い.時間が多すぎると無視できる違いがあるかもしれませんが、500ノードなので3重forゲートの切り替え作業が多すぎるので微妙な違いでタイムアウトするかどうかが決まります^ㅠ