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