Volume 5 / 0526
情報オリンピック 2007予選 解答
Problem 0526 : Boat Travel / 船旅
最短経路問題。
新しい運行情報がある度に、そこを経由する経路を更新する。
#include <iostream> #include <vector> using namespace std; vector< vector<int> > p; void refresh( int n, int a, int b ){ int i, j, k; for( i=1; i<=n; i++ ){ for( j=1; j<=n; j++ ){ if( p[i][a] != -1 && p[b][j] != -1 ) if( p[i][j] == -1 || p[i][j] > p[i][a] + p[a][b] + p[b][j] ) p[i][j] = p[j][i] = p[i][a] + p[a][b] + p[b][j]; if( p[i][b] != -1 && p[a][j] != -1 ) if( p[i][j] == -1 || p[i][j] > p[i][b] + p[b][a] + p[a][j] ) p[i][j] = p[j][i] = p[i][b] + p[b][a] + p[a][j]; } } return; } int main(void) { int n, k, t, a, b, cost; int i, j; while( cin >> n >> k, n!=0 && k!=0 ){ p.clear(); p.resize(n+1); for( i=0; i<=n; i++ ) p[i].resize( n+1, -1 ); for( i=1; i<=n; i++ ) p[i][i] = 0; for( i=0; i<k; i++ ){ cin >> t >> a >> b; if( t ){ cin >> cost; if( p[a][b] == -1 || cost < p[a][b] ){ p[a][b] = p[b][a] = cost; refresh( n, a, b ); } } else { cout << p[a][b] << endl; } } } return 0; }