TopCoder SRM 471 Div2 Hard Thirteen

TopCoder 動的計画法

問題概要

N個の都市があり、各都市間の距離が隣接行列の形で与えられるとき、以下の条件を満たしながら都市0から都市N-1に移動するときの最短時間を求めよ。

  • 移動が不可能なときは-1を返せ。

各移動後の都市到着時間をT[0],T[1],...,T[m]とすると、すべてのT[i]が13の倍数にならない。

ただし、N≦50とする。

解法

Div1 Mediumと同じだけど数字が50になっただけ？
と思って同じアルゴリズムのコード書いて送ったら落ちた。


問題よく見ると到着時間だけが13の倍数にならなければよいらしい。


なので、C[i][j]に都市iに到着時間%13がjになるような時間で着いたときの最短時間を記録しながらダイクストラすればよい。


普通Div2HardってDiv1Mediumより難しいもんなんじゃ……

ソースコード

int C[50][13],g[50][50];

class Thirteen {
	public:
	int calcTime(vector <string> city) 
	{
		int n=city.size();
		
		rep(i,n)fill_n(g[i],n,0);
		rep(i,n)rep(j,n)if(city[i][j]!='#')
		{
			char c=city[i][j];
			g[i][j]=c+(isupper(c)?1-'A':27-'a');
		}
		
		rep(i,n)fill_n(C[i],13,inf);
		C[0][0]=0;
		
		priority_queue<pi> Q; Q.push(mp(0,0));
		while(!Q.empty())
		{
			int cc=Q.top().first,cur=Q.top().second; Q.pop();
			
			if(cur==n-1)return -cc;
			
			rep(i,n)if(g[cur][i])
			{
				int d=g[cur][i],nc=cc-d,nmod=(-nc)%13;
				if(nmod==0||C[i][nmod]<=-nc)continue;
				
				C[i][nmod]=-nc;
				Q.push(mp(nc,i));
			}
		}
		return -1;
	}
};