TopCoder SRM 615 Div1 Medium LongLongTripDiv1

550ptのMediumということで難しめ。
実装はさほどではないが発想が難しい。
http://community.topcoder.com/stat?c=problem_statement&pm=13090

問題

N点からなる無向グラフが与えられる。
各辺には移動にかかる(正の整数の)時間が与えられている。

同じ辺・点を何度も通っても良い場合、0番の点から(N-1)番の点にちょうど時間Tで到達することはできるか答えよ。

解法

T<=10^18と大きいので(N-1)番に到達する時間を列挙するのは無理。
なんとか状態数を落としたい。

各辺の時間D<=10000、N<=50なので、最短経路では最長でも500,000で済むはずである。
そのためTの時間をかけるにはどこかを無駄にグルグルまわって時間を浪費しなければならない。

0番から(N-1)番に行くルートがあるとするなら、0番には最低1本の辺があるはずである。
その辺の時間をEとすると、その辺を1往復行って戻ると2E時間を浪費することができる。
よって、(N-1)番の点にT-(2E*k)の時間でたどりつくことができるなら、最初に先の辺をk往復してから移動すればいいことになる。

よって、状態として(今いる点,経過時間)をすべてとるのではなく、(今いる点,経過時間 % 2E)ととり、各状態で到達できる最短の時間をDijkstraで求めればよい。
E<=10000なので状態数は50*20000=10^6。各点から49本の辺が伸びていてもなんとか間に合う。
(実際は辺の合計数が最大50本のため、各点平均2本しか辺がないのでもっと早い)。

実際には「0番からつながる辺じゃなく、もっと途中にある閉路をグルグルすることもあるのでは？」と思うが、そのような閉路があっても1周するたびに(経過時間 % 2E)の値が毎回変わるため、最大2E周まではこの操作でカバーできる。
また、1周の時間Qの閉路を2E周するなら、最初の1往復2Eの辺をQ往復すればいいので、閉路を2E周以上する必要もない。

よって、0番の点から伸びる辺長Eを用いて2Eでmodを取るだけで良い。

ll dist[51][20001];
class LongLongTripDiv1 {
	public:
	int M;
	vector<pair<int,int> > E[51];

	string isAble(int N, vector <int> A, vector <int> B, vector <int> D, long long T) {
		int x,y,z,i,j;
		FOR(x,N) E[x].clear();
		FOR(i,A.size()) {
			E[A[i]].push_back(make_pair(B[i],D[i]));
			E[B[i]].push_back(make_pair(A[i],D[i]));
		}
		
		if(E[0].empty()) return "Impossible";
		
		ll mo=2*E[0][0].second;
		cout << mo << endl;
		
		FOR(i,N) FOR(x,mo) dist[i][x]=1LL<<61;
		set<pair<ll,int> > Q;
		dist[0][0]=0;
		Q.insert(make_pair(0,0));
		
		while(!Q.empty()) {
			ll cd = Q.begin()->first;
			int cur = Q.begin()->second;
			ll cm = cd%mo;
			Q.erase(Q.begin());
			if(dist[cur][cm]!=cd) continue;
			
			FOR(i,E[cur].size()) {
				int tar=E[cur][i].first;
				ll ne=cd+E[cur][i].second;
				if(ne>T) continue;
				if(dist[tar][ne%mo]>ne) {
					dist[tar][ne%mo]=ne;
					Q.insert(make_pair(ne,tar));
				}
			}
		}
		if(dist[N-1][T%mo]<=T) return "Possible";
		return "Impossible";
	}
};

まとめ

これは本番思いつかんわ…。