Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM471 DIV2 HARD - Thirteen (この記事を編集する[管理者用])

Source

TopCoder SRM471 DIV2 HARD (1000pt)
(サーバー不調でノーゲームとなった回,問題文はArenaから見れます, ホームページには無い)

問題概要

ノード数50以下の有向グラフが与えられるので,ノード0からn-1に行く以下の制約を満たす最小距離を求める問題.
ただし,自分自身に枝をはってるかもしれない.
制約は,移動距離がT1, T2, T3という枝を通ったのであれば,
 T1, T1+T2, T1+T2+T3
のどれも13の倍数ではない.

解法

今までの距離の和%13の値を付与して,各ノードを13倍に拡張してダイクストラする.

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 INF 1000000000

class Thirteen {
public:
int calcTime(vector <string> city) {
  int i,j,k,md;
  int res=-1;
  int n = city.size();
  int c;
  int nn, nc;
  priority_queue< pair<int,int> > q;

  int edge[60][60];
  int dist[700];

  rep(i,n) rep(j,n){
    if(city[i][j]=='#') edge[i][j]=INF;
    if('A'<=city[i][j] && city[i][j]<='Z') edge[i][j]=city[i][j]-'A'+1;
    if('a'<=city[i][j] && city[i][j]<='z') edge[i][j]=city[i][j]-'a'+1+26;
  }
  rep(i,13*n) dist[i]=INF;

  dist[0]=0; q.push(make_pair(0,0));
  while(q.size()){
    k = q.top().second; c = -q.top().first;  q.pop();
    md = k%13; k /= 13;
    if(k==n-1) { res=c; break; }
    
    rep(i,n) if(edge[k][i]!=INF){
      nc = c+edge[k][i];
      nn = i*13 + (md+edge[k][i])%13;
      if(nn%13==0) continue;
      if(dist[nn] <= nc) continue;
      dist[nn] = nc;
      q.push( make_pair(-nc,nn) );
    }
  }

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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