TopCoder SRM 841 : Div1 Hard RouteOrder

どうにか解けてよかった。
https://community.topcoder.com/stat?c=problem_statement&pm=17883

問題

N点M重み付き有向辺を持つグラフが与えられる。
0番の点から(N-1)番の点に至るシンプルなパスのうち、(K+1)番目のものを答えよ。
なお、パスの順番は以下で定める。

• 重さの総和が小さいパスが順番が先。
• 重さの総和が同じ場合、パスを構成する頂点番号列の辞書順で小さい方が先。

解法

(重みの総和, パス)からなる状態を、Priority_queueに詰めて、重みの総和の小さい順に遷移先を総当たりする。
ただし、

• 同じ頂点には2回到達しない。(以下のコードでは、パスを構成する頂点をbitmaskで表現し、判定を高速化している)
• 各頂点は、重さの総和が小さい順から(K+2)番目以降のケースは、探索を打ち切る。

こうすると到達する状態は高々O(KM)通りなので間に合う。

vector<pair<int,int>> E[44];

struct path {
	ll mask;
	int sum;
	int cur;
	string S;
};

vector<path> C;
struct Cmp {
	bool operator()(int L,int R) const
    {
	if(C[L].sum<C[R].sum) return 0;
	if(C[L].sum>C[R].sum) return 1;
	return C[L].S>C[R].S;
    }
};

int D[41*10002];


class RouteOrder {
	public:
	vector <int> findPath(int N, vector <int> X, vector <int> Y, vector <int> L, int K) {
		int i;
		int F[44]={};
		FOR(i,N) E[i].clear();
		FOR(i,X.size()) E[X[i]].push_back({Y[i],L[i]});
		FOR(i,N) sort(ALL(E[i]));
		
		C.clear();
		C.resize(100*100*10);
		int nex=1;
		C[0].mask=1;
		C[0].sum=C[0].cur=0;
		C[0].S.push_back(0);
		priority_queue<int,vector<int>,Cmp> Q;
		Q.push(0);
		
		while(Q.size()) {
			int cur=Q.top();
			Q.pop();
			
			F[C[cur].cur]++;
			if(F[C[cur].cur]>101) continue;
			
			if(C[cur].cur==N-1) {
				if(K==0) {
					vector<int> R;
					FORR(c,C[cur].S) R.push_back((int)c);
					return R;
				}
				K--;
				continue;
			}
			FORR(a,E[C[cur].cur]) {
				int e=a.first;
				int c=a.second;
				if(C[cur].mask&(1LL<<e)) continue;
				C[nex].mask = C[cur].mask | (1LL<<e);
				C[nex].sum = C[cur].sum + c;
				C[nex].cur = e;
				C[nex].S=C[cur].S+(char)e;
				Q.push(nex);
				nex++;
				
				if(nex+5>=C.size()) C.resize(C.size()*2);
			}
			
		}
		return {};
		
	}
}

まとめ

手間取ったけど解けてよかったね。