TopCoder SRM615 DIV1 MEDIUM - LongLongTripDiv1

Source

TopCoder SRM615 DIV1 MEDIUM (550pt)
Problem Statement

問題概要

ノード数 $N$，枝数 $M$ の無向グラフが与えられる．
各枝には，距離 $D_k$ が付随している．
ノード $0$ からノード $N-1$ に移動する，長さの総和がちょうど $T$ となるパスが存在するかどうかを判定する問題．
同じノードや，始点，終点を何回通っても良い．

解法

ノード $0$ に繋がっている枝がなければ不可能．
ノード $0$ に繋がっている枝のうち，適当な1つの長さを $x$ とする．
長さの総和がちょうど $t$ で移動できるなら，ちょうど $t+2x, t+4x, \ldots$ などでも移動できる．（最初にその枝を行ったり来たりすれば良い）
そこで，各ノードについて，そこまでの長さの総和の ${\rm mod}\ 2x$ がある値になるような最短路を全て求めてやれば良い．
最終的に，ノード $N-1$ に，そこまでの長さの総和の ${\rm mod}\ 2x$ が $T\ {\rm mod}\ 2x$ で行く最短路が $T$ 以下なら，ちょうど長さの総和 $T$ でノード $N-1$ に行くことができるということになる．
適当にダイクストラすることで $O((N+M) D_k \log ((N+M) D_k))$ 程度．

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

// #includeなどは略しています
#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 1000000000

template <class T>
struct DijkstraHeap {
  int *hp, *place, size; char *visited; T *val;

  void malloc(int N){hp=(int*)malloc(N*sizeof(int));place=(int*)malloc(N*sizeof(int));visited=(char*)malloc(N*sizeof(char));val=(T*)malloc(N*sizeof(T));}
  void free(){free(hp);free(place);free(visited);free(val);}
  void* malloc(int N, void *workMemory){hp=(int*)workMemory;place=(int*)(hp+N);visited=(char*)(place+N);val=(T*)(visited+N);workMemory=(void*)(val+N);return workMemory;  }
  void init(int N){int i;size=0;rep(i,N)place[i]=-1,visited[i]=0;}
  void up(int n){int m;while(n){m=(n-1)/2;if(val[hp[m]]<=val[hp[n]])break;swap(hp[m],hp[n]);swap(place[hp[m]],place[hp[n]]);n=m;}}
  void down(int n){int m;for(;;){m=2*n+1;if(m>=size)break;if(m+1<size&&val[hp[m]]>val[hp[m+1]])m++;if(val[hp[m]]>=val[hp[n]]) break;swap(hp[m],hp[n]);swap(place[hp[m]],place[hp[n]]);n=m;}}
  void change(int n, T v){if(visited[n]||(place[n]>=0&&val[n]<=v))return;val[n]=v;if(place[n]==-1)place[n]=size,hp[size++]=n,up(place[n]);else up(place[n]);}
  int pop(void){int res=hp[0];place[res]=-1;hp[0]=hp[--size];place[hp[0]]=0;down(0);visited[res]=1;return res;}
};

int memR[5000000];

class LongLongTripDiv1 {
public:
string isAble(int N, vector <int> A, vector <int> B, vector <int> D, ll T) {
  int i, j, k, M;
  int x, ni, nj; ll nc;
  int es[100], edge[100][100], dist[100][100];
  int MD;
  DijkstraHeap<ll> hp;

  M = A.size();

  rep(i,N) es[i] = 0;
  rep(k,M){
    i = A[k]; j = B[k];
    edge[i][es[i]] = j; dist[i][es[i]++] = D[k];
    edge[j][es[j]] = i; dist[j][es[j]++] = D[k];
  }

  if(es[0]==0 || es[N-1]==0) return "Impossible";
  MD = dist[0][0] * 2;
  REP(i,1,es[0]) MD = min(MD, dist[0][i] * 2);
  rep(i,es[N-1]) MD = min(MD, dist[N-1][i] * 2);

  hp.malloc(MD*N, memR);
  hp.init(MD*N);

  hp.change(0, 0);

  while(hp.size){
    k = hp.pop();

    i = k/MD; j = k%MD;
    rep(x, es[i]){
      ni = edge[i][x];
      nc = hp.val[k] + dist[i][x];
      nj = nc % MD;

      hp.change(ni*MD+nj, nc);
    }
  }

  if(hp.visited[(N-1)*MD+T%MD] && hp.val[(N-1)*MD+T%MD] <= T) return "Possible";

  return "Impossible";
}

}

Current time: 2024年04月19日04時58分26秒
Last modified: 2014年04月05日18時44分58秒 (by laycrs)
Tags: Competitive_Programming TopCoder Single_Round_Match SRM615 SRM_Div1_Medium Graph_Theory Dijkstra
トップページに戻る

Logged in as: unknown user (not login)

ログイン：