1769 ProblemBアルゴリズム7-16:フロイド最短パスアルゴリズム

質問B:アルゴリズム7-16:フロイド最短パスアルゴリズム
時間制限:1 Secメモリ制限:32 MBコミット:98解決:59
タイトルの説明
重み付き有向図Gでは,Gのいずれかの対の頂点間の最短経路を求める問題もよく見られる問題である.
この問題を解決する1つの方法はn回のディジェストラアルゴリズムを実行することであり,これにより各対の頂点間の最短経路を求めることができ,実行時間の複雑さはO(n 3)である.
もう1つのアルゴリズムはフロイドによって提案され,時間的複雑度は同様にO(n 3)であるが,アルゴリズムの形式は非常に簡単である.
フロイドアルゴリズムは次のように記述できます.
本題では、有向図の重み付き隣接行列(すなわち配列表現)を読み込み、有向図を確立し、以上の説明のアルゴリズムに従って各対の頂点間の最短経路長を求める.
 
入力
入力された最初の行は1つの正の整数nを含み、図にはn個の頂点があることを示す.ここでnは50を超えない.
以降のn行の各行には、スペースで区切られたn個の整数がある.i行目のj番目の整数について、0より大きい場合、i番目の頂点はj番目の頂点を指す有向辺があり、重み値は対応する整数値であることを示す.この整数が0である場合、iがjを指す有向辺がないことを示す.iとjが等しい場合、対応する整数が0であることを保証する.
しゅつりょく
n行が共有され、各行にはn個の整数があり、ソースポイントから各頂点までの最短パス長を表します.ソースポイントから対応する頂点へのパスが存在しない場合は、-1を出力します.頂点からそれ自体までの最短パス長に対して0を出力します.
各整数の後にスペースを出力し、行の最後に改行を出力することに注意してください.
サンプル入力

4
0 3 0 1
0 0 4 0
2 0 0 0
0 0 1 0

サンプル出力

0 3 2 1 
6 0 4 7 
2 5 0 3 
3 6 1 0 

ヒント
この問題では,問題記述のアルゴリズムに従ってフロイドアルゴリズムを完成させ,最短経路を計算する過程で各頂点が各対の頂点の最短経路を求めるまで記録できるかどうかが必要である.
ディジェストラアルゴリズムに比べて、フロイドアルゴリズムの形式はもっと簡単です.3重サイクルにより,フロイドアルゴリズムは各対の頂点間の最短距離を容易に求めることができる.
また,頂点間の到達不能状態をより容易に表すために,非常に大きな値をタグとして用いることができることに注意すべきである.一方,主題記述におけるアルゴリズム例は,元のO(n 3)時間の複雑さをO(n 4)に増大させる別の3次元配列を用いて表現され,これも自己修正が必要な部分である.
経験の総括
クラシックなフロイドアルゴリズム...この問題はやはり注意しなければならない点で、頂点から頂点自体が0であることは達成できないことを意味しないが、頂点から他の点が0であることは達成できないので、入力時に頂点から他の点に到達できないことをINFに付与しなければならない.そうすれば、フロイドアルゴリズムを楽しく使用することができる.
正しいコード

#include 

const int maxn=60;
const int INF=0x3fffffff;
int n,d[maxn][maxn];
void Floyd()
{
	for(int k=0;k