AOJ 0526 Boat Travel

404 Not Found

JOI過去問。昨日くらいに解いた。経路情報管理には隣接行列を用いるのが楽。

問題文読んでからコーディング時間計測開始、全力の高速実装で10分強+くだらないバグ見つけるのに20分くらい掛かった。

いろいろと無駄の多いソース。dijkstra。

#include <iostream>
#include <queue>
#include <vector>
#include <climits>
using namespace std;
typedef pair<long long,int> NODE;
#define cost first
#define pos second
#define INF INT_MAX

int n;
long long info[100][100];

long long dijkstra(int a,int b){
	priority_queue<NODE,vector<NODE>,greater<NODE> > Q;
	Q.push( make_pair(0,a) );
	
	long long memo[100];
	for(int i=0;i<100;i++)memo[i]=INF;
	memo[a]=0;
	
	while(Q.size()){
		NODE q = Q.top();Q.pop();
		
		if(q.pos == b)return q.cost;
		
		for(int i=0;i<n;i++){
			if(memo[i] > q.cost+info[q.pos][i]){
				memo[i] = q.cost+info[q.pos][i];
				Q.push( make_pair(memo[i],i) );
			}
		}
	}
	return -1;
}

int main(){
	int k,a,b,c,r;
	while(cin >> n >> k && n || k){
		for(int i=0;i<100;i++)for(int j=0;j<100;j++)
			info[i][j]=INF;
			
		for(int i=0;i<k;i++){
			cin >> r;
			if(r){
				cin >> a >> b >> c;
				a--;b--;
				info[a][b] = info[b][a] = min<long long>(info[a][b],c);
			}else{
				cin >> a >> b;
				a--;b--;
				cout << dijkstra(a,b) << endl;
			}
		}
	}
}