JOI予選2014 part2

5問目

普通にDijkstraやったら通ってしまったのでなぜこの問題をやらなかったのか後悔せざる得ない。
20分位で書けてしまってテストケースすべて1発で通してしまったので萎えた。

#include<iostream>
#include<queue>
#include<vector>
#include<map>
using namespace std;
#define fr first
#define sc second
typedef pair < int , int > Pi;
struct edge{
  int limit, cost;
  vector< int > node , cango;
} info[5001];
int n, k;
bool used[5001];

int Dijkstra(){
  priority_queue< Pi , vector< Pi > , greater< Pi > > que;
  for( que.push(Pi(0,0)) ; !que.empty() ; que.pop()){
    Pi p = que.top();
    if(used[p.sc]++) continue;
    if(p.sc == n - 1) return p.fr;
    for(int i = 0 ; i < info[p.sc].cango.size() ; i++ ){
      que.push(Pi(p.fr + info[p.sc].cost,info[p.sc].cango[i]));
    }
  }
}
int main(){
  cin >> n >> k;
  for(int i = 0 ; i < n ; i++ ){
    cin >> info[i].cost >> info[i].limit;
  }
  for(int i = 0, a, b ; i < k ; i++ ){
    cin >> a >> b;
    info[--a].node.push_back(--b);
    info[b].node.push_back(a);
  }

  queue< Pi > que;
  for(int i = 0 ; fill_n(used, 5001, false), i < n ; i++ ){
    for( que.push(Pi(i,info[i].limit)) ; !que.empty() ; que.pop() ){
      Pi p = que.front();
      if(!p.sc) continue;
      for(int j = 0 ; j < info[p.fr].node.size() ; j++ ){
        if(!used[info[p.fr].node[j]]++){
          info[i].cango.push_back(info[p.fr].node[j]);
          que.push(Pi(info[p.fr].node[j],p.sc-1));
        }
      }
    }
  }
  cout << Dijkstra() << endl;
}