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; }