AOJ 0212 Highway Express Bus

404 Not Found

解けるようになっててビビった。先輩ん家で解説された時何となく言ってることは分かるけど、実装方法とかチンプンカンプンだったのに。

　 「ネタ(アルゴリズム)」を持っていると強いです。

クソ最適化されてない害クストラ

#include <iostream>
#include <queue>
#include <climits>
#include <vector>
using namespace std;
typedef pair<pair<int,int>,int> NODE;
#define cost first.first
#define ticket first.second 
#define pos second
#define ppp(a,b,c) make_pair(make_pair(a,b),c)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF (1<<21)

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

int dijk(int a,int b,int c){
	priority_queue<NODE,vector<NODE>,greater<NODE> >  Q;
	int memo[100][11];
	rep(i,100)rep(j,11)memo[i][j] = INF;
	rep(j,11)memo[a][j] = 0;
	
	Q.push(ppp(0,c,a));
	while( !Q.empty() ){
		NODE q = Q.top();Q.pop();
		for(int i=0;i<n;i++){
			if( info[q.pos][i]+q.cost < memo[i][q.ticket]){
				 memo[i][q.ticket] = info[q.pos][i]+q.cost;
				Q.push(ppp(info[q.pos][i]+q.cost ,q.ticket,i));
			}
			if( q.ticket && info[q.pos][i]/2+q.cost < memo[i][q.ticket-1] ){
					Q.push( ppp( info[q.pos][i]/2+q.cost , q.ticket-1, i));
				 memo[i][q.ticket-1] = info[q.pos][i]/2+q.cost;
			}
		}
	}
	int mi = (1<<21);
	rep(j,11)mi = min(memo[b][j],mi);
	return mi;
}
int main(){
	int c,m,s,d,a,b,f;
	while(cin >> c >> n >> m >> s >> d ,c ){
		s--;d--;
		rep(i,100)rep(j,100)info[i][j]=INF*2;
		
		for(int i=0;i<m;i++){
			cin >> a >> b >> f;
			a--;b--;
			info[a][b] = info[b][a] = f;
		}
		cout << dijk(s,d,c) << endl;
	}
}