PKU 2982 Time Travel

http://poj.org/problem?id=2982
原点から座標(n,m)まで移動するのにかかるコストを求めろというような問題。
ただし、途中で原点と座標(n,m)で作れる長方形から出てはいけない。

ダイクストラしました。
好き勝手に移動していてTLEやらWAやらをもらいまくりました。

bool vis[110][10000];
int a[110],b[110],c[110];
int n,m,k;

void solve(){
  memset(vis,0,sizeof(vis));
  rep(i,k)
    scanf("%d%d%d",a+i,b+i,c+i);

  priority_queue<pair<int,PI> >q;
  q.push(mp(0,mp(0,0)));
  //m+=5000;
  while(!q.empty()){
    int cc=-q.top().F;
    int cx=q.top().S.F;
    int cy=q.top().S.S;
    q.pop();
    if(cy<0 || cy>m)continue;
    for(;0 > cy || cy>=10000;);
    if(vis[cx][cy])continue;
    vis[cx][cy]=true;
    if(cx==n && cy==m){
      cout<<cc<<endl;
      return;
    }
    rep(i,k)
      if(cx+a[i]<=n)
        q.push(mp(-cc-c[i],mp(cx+a[i],cy+b[i])));
  }
  cout<<-1<<endl;
}

main(){
  while(cin>>n>>m>>k,n|m|k)
    solve();
}