2151-Brave Princess Revisited

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2151&lang=jp
考え方
現在居る宿屋と残りの所持金でBFSする。

実装(C++)

bool accessed[101][101];
typedef pair<int,int> Q;
typedef pair<int,Q> P;
int solve(Graph &G){
	priority_queue<P,vector<P>,greater<P> > que;
	memset(accessed,0,sizeof(accessed));
	P s;s.first=0;s.second.first=0;s.second.second=l;
	que.push(s);
	while(!que.empty()){
		s=que.top();que.pop();
		if(accessed[s.second.first][s.second.second])continue;
		accessed[s.second.first][s.second.second]=1;
		if(s.second.first==n-1)return s.first;
		for(int i=0;i<(int)G[s.second.first].size();i++){
			if(G[s.second.first][i].cost<=s.second.second){
				que.push(P(s.first,Q(G[s.second.first][i].dst,s.second.second-G[s.second.first][i].cost)));
			}
			que.push(P(s.first+G[s.second.first][i].enemy,Q(G[s.second.first][i].dst,s.second.second)));
		}
	}
}

int main() {
	for(;cin>>n>>m>>l;){
		if(n==0)break;
		Graph G(n);
		for(int i=0;i<m;i++){
			int a,b,d,e;
			cin>>a>>b>>d>>e;a--;b--;
			G[a].push_back(Edge(a,b,d,e));
			G[b].push_back(Edge(b,a,d,e));
		}
		cout << solve(G) << endl;
	}
	return 0;
}