0526-Boat Travel

　Project Eularに逃避していました。
ダイクストラで解答したところ、あまり速度が出なかった。
解説を読んだらワーシャルフロイドっぽいアルゴリズムで解いていたので、そのようにしたところ4倍ぐらい速くなった。

実装(C++/Include省略)

const lli INF=0x3B9ACA00;
uint d[MAX_V][MAX_V];
int n,k,t,t1,t2,t3,c;
edge tmped;
int getd(int x,int y){
	if(x>y)return d[y][x];
	return d[x][y];
}
int main(){
	for(;;){
		n=readint();k=readint();
		if((n|k)==0) break;
		memset(d,0x7F,sizeof(d));
		for(int i=0;i<n;i++){
			d[i][i]=0;
		}
		for(int i=0;i<k;i++){
			t=readint();
			if(t==1){
				c=1;
				t1=readint()-1;t2=readint()-1;t3=readint();
				if(d[t1][t2]>t3){
					d[t1][t2]=t3;
					d[t2][t1]=t3;

					for(int x=0;x<n;x++){
						for(int y=0;y<n;y++){
							d[x][y]=min(min(d[x][y],d[x][t1]+d[t1][t2]+d[t2][y]),d[x][t2]+d[t2][t1]+d[t1][y]);
						}
					}
				}
			} else {
				t1=readint()-1;t2=readint()-1;
				if(d[t1][t2]>INF){
					fwrite("-1\n", 1, 3, stdout);
				} else {
					puti(d[t1][t2]);
				}
			}
		}
	}
}