/*
Copyright 2011 Marek "p2004a" Rusinowski
Floyd-Warshall algorithm
*/
#include <cstdio>
#include <algorithm>
#define MAXN 1000
#define INF 0x0FFFFFFF
int d[ MAXN] [ MAXN] ;
int main( ) {
int n, m, a, b, c;
scanf ( "%d %d" , & n, & m) ;
std:: fill ( ( int * ) d, ( int * ) d + MAXN * n, INF) ;
for ( int i = 0 ; i < n; ++ i) {
d[ i] [ i] = 0 ;
}
for ( int i = 0 ; i < m; ++ i) {
scanf ( "%d %d %d" , & a, & b, & c) ;
d[ -- a] [ -- b] = c;
d[ b] [ a] = c;
}
for ( int k = 0 ; k < n; ++ k) {
for ( int i = 0 ; i < n; ++ i) {
for ( int j = 0 ; j < n; ++ j) {
d[ i] [ j] = std:: min ( d[ i] [ j] , d[ i] [ k] + d[ k] [ j] ) ;
}
}
}
for ( int j = 0 ; j < n; ++ j) {
for ( int i = 0 ; i < n; ++ i) {
printf ( "%3d " , d[ j] [ i] ) ;
}
printf ( "\n " ) ;
}
return 0 ;
}
LyoKICBDb3B5cmlnaHQgMjAxMSBNYXJlayAicDIwMDRhIiBSdXNpbm93c2tpCiAgRmxveWQtV2Fyc2hhbGwgYWxnb3JpdGhtCiovCiNpbmNsdWRlIDxjc3RkaW8+CiNpbmNsdWRlIDxhbGdvcml0aG0+CgojZGVmaW5lIE1BWE4gMTAwMAojZGVmaW5lIElORiAweDBGRkZGRkZGCgppbnQgZFtNQVhOXVtNQVhOXTsKCmludCBtYWluKCkgewogIGludCBuLCBtLCBhLCBiLCBjOwogIHNjYW5mKCIlZCAlZCIsICZuLCAmbSk7CiAgc3RkOjpmaWxsKChpbnQqKWQsIChpbnQqKWQgKyBNQVhOICogbiwgSU5GKTsKICBmb3IgKGludCBpID0gMDsgaSA8IG47ICsraSkgewogICAgZFtpXVtpXSA9IDA7CiAgfQogIGZvciAoaW50IGkgPSAwOyBpIDwgbTsgKytpKSB7CiAgICBzY2FuZigiJWQgJWQgJWQiLCAmYSwgJmIsICZjKTsKICAgIGRbLS1hXVstLWJdID0gYzsKICAgIGRbYl1bYV0gPSBjOwogIH0KICBmb3IgKGludCBrID0gMDsgayA8IG47ICsraykgewogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBuOyArK2kpIHsKICAgICAgZm9yIChpbnQgaiA9IDA7IGogPCBuOyArK2opIHsKICAgICAgICBkW2ldW2pdID0gc3RkOjptaW4oZFtpXVtqXSwgZFtpXVtrXSArIGRba11bal0pOwogICAgICB9CiAgICB9CiAgfQogIGZvciAoaW50IGogPSAwOyBqIDwgbjsgKytqKSB7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IG47ICsraSkgewogICAgICBwcmludGYoIiUzZCAiLCBkW2pdW2ldKTsKICAgIH0KICAgIHByaW50ZigiXG4iKTsKICB9CiAgcmV0dXJuIDA7Cn0K
compilation info
prog.cpp: In function ‘int main()’:
prog.cpp:15: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
prog.cpp:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
stdout
0 1 2 3
1 0 1 2
2 1 0 1
3 2 1 0