AOJ 0212 Highway Express Bus

問題

Highway Express Bus

解法

拡張ダイクストラ法。初めて解いた。拡張グラフのダイクストラとかなんとか、

グラフを３次元方向に掘ってく

心臓に悪いコード

typedef pair<int, int> pi; // 残りの割引券 現在の街
typedef pair<int, pi>P; // コスト pi

struct edge{ int to, cost; };

int C, V, E, S, D;
int d[128][16];
vector<vector<edge> >G(128);

void dijkstra(int s){
  priority_queue<P, vector<P>, greater<P> >q;
  rep(i, V) rep(j, C+1) d[i][j] = INF;
  d[s][C] = 0;
  q.push(MP(0, MP(C, s)));

  while(!q.empty()){
    P p = q.top(); q.pop();
    int v = p.S.S;
    int c = p.S.F;

    rep(i, G[v].size()){
      edge e = G[v][i];
      if(d[e.to][c] > d[v][c] + e.cost){
    d[e.to][c] = d[v][c] + e.cost;
    q.push(MP(d[e.to][c], MP(c, e.to)));
      }

      if( c > 0 && d[e.to][c-1] > d[v][c] + e.cost/2){
      d[e.to][c-1] = d[v][c] + e.cost/2;
      q.push(MP(d[e.to][c-1], MP(c-1, e.to)));
      }
    }
  }
}

int main(){
  while(scanf("%d%d%d%d%d", &C, &V, &E, &S, &D) && C+V+E+S+D){
    S--; D--;
    rep(i, 128){
      G[i].clear();
    }

    rep(i, E){
      int a, b, c;
      scanf("%d%d%d", &a, &b, &c); a--; b--;
     edge e;
      e.to = a; e.cost = c;
      G[b].PB(e);
      e.to = b;
      G[a].PB(e);
    }

    dijkstra(S);

    int res = INF;
    rep(i, C+1) res = min(res, d[D][i]);
    printf("%d\n", res);
  }
  return 0;
}