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: 2017年11月23日18時28分11秒
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)

ログイン: