Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1477-90723951
この記事にトラックバックする(FC2ブログユーザー)

Open 2010 Round 5 MEDIUM - LongJourney (この記事を編集する[管理者用])

Source

TopCoder Open 2010 Algorithm Round 5 MEDIUM (500pt)
Problem Statement
Open 2010 Algorithm Round 5 自分の参加記録

問題概要

50ノード以下の無向グラフが与えられる.
それぞれのノードで燃料1あたりいくらで買えるかも与えられる.
ノード0からノード1に辿りつくまでの最小コストを求める問題.
燃料タンクの上限値は1000000.

解法

残り燃料の量でノードを拡大してダイクストラする.
ただし,残り燃料を1刻みで燃料タンクの上限値まで考えるとノード数が50*1000000になって間に合わない.
残り燃料は,0,燃料タンク満タンと,他のノードまでの最短距離だけ考えれば十分なので,これならノード数が50*51になる.

C++によるスパゲッティなソースコード

このコードは実際に本番でサブミットしたコードです.見にくいと思われます.

// #includeとusing namespace std;は略

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long
#define INF 1000000000000000LL

void llSort(ll d[],int s){int i,j;ll k,t;if(s<=1)return;k=(d[0]+d[s-1])/2;i=-1;j=s;for(;;){while(d[++i]<k);while(d[--j]>k);if(i>=j)break;t=d[i];d[i]=d[j];d[j]=t;}llSort(d,i);llSort(d+j+1,s-j-1);}

class LongJourney {
public:
ll minimumCost(vector <int> fuelPrices, int fuelTank, vector <string> roads) {
  int i,j,k; ll n,per,ff;
  ll a,b;
  ll st=0;
  ll cost, next;
  ll res;
  ll dist[51][52];
  ll lst[51][52];
  ll dp[52][52];
  priority_queue<pair<ll,int> > q;
  string str;

  n=fuelPrices.size();
  rep(i,n) rep(j,n) dist[i][j]=INF; rep(i,n) dist[i][i]=0;

  rep(i,roads.size()) str += roads[i];

  for(;st<str.size();){
    sscanf(str.c_str()+st,"%d,%d,%d",&i,&j,&k);
    if(dist[i][j]>k) dist[i][j]=dist[j][i]=k;
    while(st<str.size() && str[st]!=' ') st++;
    st++;
  }

  per = n+1;

  rep(k,n) rep(i,n) rep(j,n) if(dist[i][j]>dist[i][k]+dist[k][j]) dist[i][j]=dist[i][k]+dist[k][j];
  
  rep(i,n) rep(j,n){
    lst[i][j] = dist[i][j];
    lst[i][n] = fuelTank;
  }
  rep(i,n) llSort(lst[i],per);

  rep(i,n) rep(j,per) dp[i][j]=INF;
  dp[0][0]=0;
  q.push( make_pair(0LL,0) );

  while(q.size()){
    k=q.top().second;
    cost = -q.top().first;
    q.pop();
    i = k/per; j = k%per;
    if(dp[i][j] < cost) continue;

    if(j+1 != per) if(lst[i][j+1]<=fuelTank) {
      next = cost + fuelPrices[i] * (ll)(lst[i][j+1]-lst[i][j]);
      if(dp[i][j+1] > next){
        dp[i][j+1] = next;
        q.push( make_pair(-next, i*per+j+1) );
      }
    }

    rep(a,n) if(a!=i){
      ff = lst[i][j] - dist[i][a];
      if(ff<0) continue;
      for(b=0;;b++) if(lst[a][b] >= ff) break;
      next = cost + fuelPrices[a] * (ll)(lst[a][b]-ff);
      if(dp[a][b] > next){
        dp[a][b]=next;
        q.push( make_pair(-next, a*per+b) );
      }
    }
  }

  res = INF;
  rep(i,per) if(res > dp[1][i]) res = dp[1][i];
  if(res==INF) res=-1;

  return res;
}

};

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1477-90723951
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。