Petitverse

REM ベホマ
REM 前のやつより遅いかも
ACLS
XSCREEN 1
OPTION STRICT
OPTION DEFINT
VAR N,M
DIM X[30000],Y[30000],T[30000]
DIM D[100]
VAR I,J
VAR INF=1000000
VAR ANS=0

INPUT N,M
FOR I=0 TO M-1
　INPUT X[I],Y[i],T[i]
NEXT I
FOR I=1 TO N-1
　D[I]=INF
NEXT I
FOR I=1 TO N-1
　FOR J=0 TO M-1
　　D[Y[J]]=MIN(D[Y[J]],D[X[J]]+T[J])
　NEXT J
NEXT I

FOR I=0 TO N-1
　ANS=MAX(ANS,D[I])
NEXT I

PRINT ANS

SatoshiMcCloudさん
これは初代ダイクストラ法かな。きれいなコードだ…
文句なしの正解です。

ツララさん
>無線で配信(中略)特定すればいいんじゃないんです？
　その部分をどうやって実装するのか気になったので、トピックを建てました。
>というか、受信した端末が他の端末に向けて自動的に再送信するってどこにも書いてないですよね。
　結局受信したと同時に他の端末に向けて送信するのが一番かかる時間が短くなります。(そうでないと直感的に嫌な気分になります)
>あと最低限必要なアンテナの数のMってNの数が決まればN*(N-1)で求めれますよね。
　最低限必要なアンテナの数は0番目の端末から1,2,…N-1番目の端末にそれぞれ直接送信するのが一番少なく済むので、N-1本で合ってると思います。

REM 見せてやるぜ…†本物のダイクストラ法†ってやつをよ…
REM なお動作は未検証
ACLS
XSCREEN 1
OPTION STRICT
OPTION DEFINT
VAR N,M
VAR X,Y,T
DIM LIST[3100],NODE[3100],COST[3100]
VAR LLAST
DIM HEAP[3100],HDIST[3100]
VAR HLAST
DIM D[100]
VAR INF=1000000
VAR I,J
VAR LOOK
VAR P
VAR ANS

INPUT N,M
LLAST=N
FILL D,INF,0,N
FOR I=1 TO M
　INPUT X,Y,T
　LIST[LLAST]=LIST[X]
　LIST[X]=LLAST
　NODE[LLAST]=Y
　COST[LLAST]=T
　LLAST=LLAST+1
NEXT I

HEAP[0]=0
HLAST=1
D[0]=0
WHILE HLAST
　'POP
　LOOK=HEAP[0]
　IF HDIST[0]<D[LOOK] THEN D[LOOK]=HDIST[0]
　HLAST=HLAST-1
　T=HEAP[HLAST]
　I=0
　J=1+(heap[1]>heap[2])
　while J<HLAST&&T>HEAP[J]
　　HEAP[I]=HEAP[J]
　　HDIST[I]=HDIST[J]
　　I=J
　　IF J*2+1<LAST&&HEAP[J*2+1]>HEAP[J*2+2] THEN
　　　J=J*2+1
　　ELSE
　　　J=J*2+1
　　ENDIF
　WEND
　HEAP[I]=T

　P=LIST[LOOK]
　T=D[LOOK]
　WHILE P
　　IF T+COST[P]<D[NODE[P]] THEN
　　　'PUSH
　　　I=HLAST
　　　J=(I-1)>>1
　　　WHILE I>0&&HEAP[J]>N
　　　　HEAP[I]=HEAP[J]
　　　　HDIST[I]=HDIST[J]
　　　　I=J
　　　　J=(I-1)>>1
　　　WEND
　　　HEAP[I]=NODE[P]
　　　HDIST[I]=T+COST[P]
　　　HLAST=HLAST+1
　　ENDIF
　　P=LIST[P]
　WEND
WEND
FOR I=0 TO N-1
　ANS=MAX(ANS,D[I])
NEXT I
PRINT ANS

この問題の内容をまとめると、「グラフが与えられるので、ある始点から全ての頂点までの最短経路を答える(そしてその最短経路の最大値を答える)」問題になっています。
こういった問題を単一始点最短経路問題と言い、いくつかの効率的なアルゴリズムが知られています。
単一始点最短経路問題を解く最も一般的なアルゴリズムとして、ダイクストラ法が挙げられます。
ダイクストラ法は、始点からの距離が近い順に最短距離を決めていくアルゴリズムで、ヒープと隣接リストと呼ばれるデータ構造を用いることで効率的に実装することができます。
ヒープとは
・値を追加する
・追加された値の中から最小値を取り出す
といった操作を効率的に行うことが出来るデータ構造で、今回の場合、二分ヒープや、radix heapと呼ばれるヒープを使うと効果的です。
隣接リストとは、グラフにおいてある頂点から出ている辺を各頂点について持つデータ構造で、「ある頂点から出ている全ての辺を調べる」といった操作を効率的に行うことが出来ます。リストの配列や、可変長配列の配列を使うことで実装出来ますが、プチコンだとどちらも少し工夫が必要です。(実はこの実装をどうやるかが見たかった)僕の解答では、前者を利用しています。

ダイクストラの手順は、
ヒープに始点と距離0を追加する
while ヒープが空でない間
　ヒープから頂点と距離を取り出す。
　IF 距離がその頂点の暫定の距離より短いなら
　　距離を更新する。
　　while 取り出した頂点から出る全ての辺に対して
　　　IF 始点から辺の終点のまでの距離>取り出した頂点までの距離+辺の重みなら
　　　　ヒープに頂点と、距離+辺の重みを追加する
といった手順です。
(続く)

最短経路問題を解くアルゴリズムは他にもベルマンフォード法やフロイドワ―シャル法と言ったアルゴリズムが知られています。
ダイクストラ法は、辺の重みが負の場合は使えませんが、ベホマやフロイドワ―シャルは、辺の重みが負の場合でも使うことが出来ます。
d[i]を頂点iまでの暫定の最短経路とした場合、
ベルマンフォード法は、全ての辺に対して
d[y]=d[x]+t
といった操作を繰り返すことで、最短経路を求めるアルゴリズムです。
全ての辺に対して上の操作を1回行うごとに、距離が短い頂点から順に1頂点づつ最短経路が確定していくため、頂点数×辺の数の計算量で最短経路が求まります。

フロイドワ―シャル法は、単一始点最短経路ではなく、全ての辺間の最短経路を求める問題です。仕組みは難解ですが、実装は楽なので、計算量に余裕があれば単一始点最短経路問題に使われることもあります。というか、今回の場合、ベホマより速いです。
フロイドワ―シャル法は、グラフを隣接行列と呼ばれるデータ構造で管理します。
隣接行列は、全ての頂点の組(j,k)に対してjからkに向かう辺があるかどうかを高速に調べることができるデータ構造で、二次元配列を使って実装されます。
フロイドワ―シャル法の原理は難解なので省きますが、
全ての頂点の組(j,k)に対して、頂点iを経由した経路のコストが、暫定のjからkのコストより小さい場合は、jからkのコストをiを経由したコストに置き換えるといった動作を繰り返します。
フロイドワ―シャル法は、ループの順番が重要ですが、間違った書き方をしても、3回書くことで正しい動作になることが知られています。