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;
}