JOI2008予選 問題6＠C++(5)

最短距離の表を保持して、更新があるごとに隣接パスとの合計距離を再計算して更新キューに積む。
ダイクストラって言うんだっけ？いや違うかなあ。
対称テーブルはSTLには無いのかなあ。というわけで自分で実装。
あと、queueの辺りでpairが暴走してて困る。

#include <climits>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

template <typename T>
class symtable
{
private:
	int _size;
	vector<vector<T> > innerTable;
public:
	T& at(int x,int y) {
		if(x<y)swap(x,y);
		return innerTable[x][y];
	}
	int size() {
		return size;
	}
	symtable(int size,const T& init) : _size(size),innerTable(size,vector<T>(size,init)) {
		
	}
};

int main(int argc,char* argv[])
{
	int n,k;
	scanf("%d %d\n",&n,&k);
	symtable<int> table(n,1000001);
	for(int i=0;i<k;i++) {
		char prefix;
		scanf("%c ",&prefix);
		if(prefix=='0') {
			int a,b;
			scanf("%d %d\n",&a,&b);
			a--;
			b--;
			int charge=table.at(a,b);
			if(charge==1000001) charge=-1;
			printf("%d\n",charge);
		} else if(prefix=='1') {
			int c,d,e;
			scanf("%d %d %d\n",&c,&d,&e);
			c--;
			d--;
			queue<pair<pair<int,int>,int> > que;
			que.push(make_pair(make_pair(c,d),e));
			while(!que.empty()) {
				int to=que.front().first.first;
				int from=que.front().first.second;
				int charge=que.front().second;
				que.pop();
				if(charge<table.at(to,from)) {
					table.at(to,from)=charge;
					for(int j=0;j<n;j++) {
						if(j==to || j==from)continue;
						que.push(make_pair(make_pair(to,j),charge+table.at(from,j)));
						que.push(make_pair(make_pair(from,j),charge+table.at(to,j)));
					}
				}
			}
		}
	}
	return 0;
}