PKU 3635 Full Tank?

http://poj.org/problem?id=3635
ある街からある街まで燃料を補充しながら、最小のコストで移動したい。
距離を持つ無向グラフと、各ノードでの1ユニットの燃料補充にかかる値段が予め与えられる。

このとき、保持できる最大の燃料と、スタート地点、ゴール地点のクエリに対して最小のコストを答えろというような問題。

現在地と持ってる燃料でダイクストラしました。
計算量的にちょっと大きいかとも思いましたが、そこまで時間が厳しいわけではないようです。

bool vis[1000][103];
int pr[1000];

vector<PI> G[1000];

void solve(){
  int c,s,e;
  cin>>c>>s>>e;
  memset(vis,0,sizeof(vis));
  priority_queue<pair<int,PI> >q;
  q.push(mp(0,mp(s,0)));

  while(!q.empty()){
    int cc=-q.top().F;
    int tv=q.top().S.F;
    int cap=q.top().S.S;
    q.pop();
    if(tv==e){
      printf("%d\n",cc);
      return;
    }
    if(vis[tv][cap])continue;
    vis[tv][cap]=true;
    if(cap<c && !vis[tv][cap+1])
      q.push(mp(-cc-pr[tv],mp(tv,cap+1)));

    FOR(it,G[tv]){
      int to=it->F;
      int d=it->S;
      if(d>cap ||
         vis[to][cap-d])continue;
      q.push(mp(-cc,mp(to,cap-d)));
    }
  }
  
  cout<<"impossible"<<endl;
}

main(){
  int n,m;
  cin>>n>>m;
  rep(i,n)
    cin>>pr[i];

  rep(i,m){
    int u,v,d;
    cin>>u>>v>>d;
    G[u].pb(mp(v,d));
    G[v].pb(mp(u,d));
  }

  int q;
  cin>>q;
  while(q--)
    solve();
}