TopCoder SRM 624 Div1 Medium DrivingPlans

せっかく450ptで定番問題っぽかったのに落とした…。
http://community.topcoder.com/stat?c=problem_statement&pm=13197

問題

N頂点の連結グラフが与えられ、各無向辺には移動にかかる時間が与えられる。
0番の頂点から(N-1)番の頂点に移動する最短路は何通り考えられるか。

解法

頂点x,y間の移動経路移動時間をT(x,y)とする。
まず２回Dijkstraを行い、各頂点xにおいてT(0,x)とT(x,N-1)を求める。
ある頂点xが最短路上に存在しうるのは、T(0,x)+T(x,N-1)==T(0,N-1)の場合である。

もしxが最短路上にあり、かつxから時間0の辺が伸びていた場合、その辺を何往復しても移動時間が伸びないので、最短路は無限大に存在する。
それ以外の場合は、再度Dijkstraを行い、最短路をたどりながらDPして数え上げを行えばよい。

以下のコードでは、T(0,x)の算出と数え上げを同時に行っている。

vector<pair<int,int> > E[2001];
ll D[2][2001];
int mult[2001];
ll pat[2001];
ll mo=1000000009;

class DrivingPlans {
	public:
	int M;
	int count(int N, vector <int> A, vector <int> B, vector <int> C) {
		M=A.size();
		int i,x;
		
		ZERO(mult);
		FOR(i,N) E[i].clear();
		FOR(i,M) E[A[i]-1].push_back(make_pair(C[i],B[i]-1));
		FOR(i,M) E[B[i]-1].push_back(make_pair(C[i],A[i]-1));
		FOR(i,M) if(C[i]==0) mult[A[i]-1]=mult[B[i]-1]=1;
		
		FOR(i,N) D[0][i]=D[1][i]=1LL<<60;
		D[0][N-1]=D[1][0]=0;
		ZERO(pat);
		pat[0]=1;
		
		priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > Q,Q2;
		FOR(x,2) {
			Q.push(make_pair(0,(x==1)?0:(N-1)));
			while(!Q.empty()) {
				pair<int,int> k=Q.top();
				Q.pop();
				int cur=k.second;
				if(k.first != D[x][cur]) continue;
				if(x==1 && D[0][cur]+D[1][cur]!=D[0][0]) continue;
				if(x==1 && mult[cur]) return -1;
				
				FOR(i,E[cur].size()) {
					int tar=E[cur][i].second;
					if(D[x][tar] > D[x][cur]+E[cur][i].first) {
						D[x][tar] = D[x][cur]+E[cur][i].first;
						Q.push(make_pair(D[x][tar],tar));
					}
					if(x==1 && D[0][cur]==D[0][tar]+E[cur][i].first) pat[tar]=(pat[tar]+pat[cur])%mo;
				}
			}
		}
		
		return pat[N-1]%mo;
	}
}

まとめ

典型問題っぽいのになぜ落とした…。