PKU 1724 ROADS
http://poj.org/problem?id=1724
n個のノードがあって、それぞれを結ぶ辺には移動距離と移動費用が指定されている。
使用可能な値段がkまでのとき、ノード1からノードnまでの最短距離を求めろというような問題。
値段と位置を保持してダイクストラしました。
vector<pair<int,PI> > G[100]; bool vis[100][10001]; main(){ int k,n,r; cin>>k>>n>>r; rep(i,r){ int s,d,l,t; cin>>s>>d>>l>>t; --s,--d; G[s].pb(mp(d,mp(l,t))); } priority_queue<pair<int,PI> >q; q.push(mp(0,mp(0,0))); while(!q.empty()){ pair<int,PI> cst=q.top(); q.pop(); if(vis[cst.S.F][cst.S.S])continue; vis[cst.S.F][cst.S.S]=true; if(cst.S.F==n-1){ cout<<-cst.F<<endl; return 0; } rep(i,SZ(G[cst.S.F])){ pair<int,PI> nst=cst; nst.F-=G[cst.S.F][i].S.F; nst.S.S+=G[cst.S.F][i].S.S; nst.S.F=G[cst.S.F][i].F; if(nst.S.S>k || vis[nst.S.F][nst.S.S])continue; q.push(nst); } } cout<<-1<<endl; }