AOJ 0526: Boat Travel

辺が増えていく最短経路問題。増えた辺を使うと経路が短くなる場合があるので、それを調べます。(増えた辺を使わないで経路が短くなることはない)
O(kn^2)です。

AOJではギリギリ通せなかったのですが、ワーシャルフロイド法(や、その他の最短路のアルゴリズム)を使っても解けます。
シンプルに書いて、1.02sだったのでAOJでは頑張っても通せなさそうです。

#include<cstdio>
#include<algorithm>
using namespace std;

int q,n,k,g[100][100],INF = 10000000;

int main(){
	while(scanf("%d%d",&n,&k),n){
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				if(i==j)g[i][j] = 0;
				else g[i][j] = INF;
			}
		}
		for(int i = 0; i < k; i++){
			scanf("%d",&q);
			if(q){
				int a,b,c;
				scanf("%d%d%d",&a,&b,&c);
				a--;b--;
				if(c<g[a][b]){
					g[a][b] = g[b][a] = c;
					for(int i = 0; i < n; i++){
						for(int j = 0; j < n; j++){
							g[i][j] = g[j][i] = min(g[i][j],g[i][a]+g[a][b]+g[b][j]);
						}
					}
				}
			}else{
				int a,b;
				scanf("%d%d",&a,&b);
				printf("%d\n",g[a-1][b-1]<INF?g[a-1][b-1]:-1);
			}
		}
	}
	
	return 0;
}

追記(2012/04/14)

コメントで指摘されたように書きなおしたら、0.80sで解けました。
最短経路が変わらない場合を忘れていました。

#include <cstdio>
#include <algorithm>
using namespace std;

int n,k,g[100][100];
const int INF = 1e9;

int main(){
	while(scanf("%d%d",&n,&k),n){
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				if(i==j)g[i][j] = 0;
				else g[i][j] = INF;
			}
		}
		bool flag = false;
		for(int i = 0; i < k; i++){
			int q;
			scanf("%d",&q);
			if(q){
				int a,b,c;scanf("%d%d%d",&a,&b,&c);
				if(c<g[a-1][b-1]){
					g[a-1][b-1] = g[b-1][a-1] = c;
					flag = true;
				}
				/*
				if文を使わずに、
				
				g[a-1][b-1] = g[b-1][a-1] = min(c,g[a-1][b-1]);
				flag = true;
				
				とすると、TLEする
				*/
			}else{
				int a,b;
				scanf("%d%d",&a,&b);
				if(flag){
					for(int k = 0; k < n; k++){
						for(int i = 0; i < n; i++){
							for(int j = 0; j < n; j++){
								g[i][j] = min(g[i][j],g[i][k]+g[k][j]);
							}
						}
					}
					flag = false;
				}
				printf("%d\n",g[a-1][b-1]<INF?g[a-1][b-1]:-1);
			}
		}
	}
	
	return 0;
}