kmjp's blog

競技プログラミング参加記です

square869120Contest #1 : G - Revenge of Traveling Salesman Problem

Fより簡単だった。
http://s8pc-1.contest.atcoder.jp/tasks/s8pc_1_g

問題

N頂点M辺のグラフが与えられる。
各辺は移動にかかる時間D[i]及び、移動可能な時間T[i]が設定されている。
(移動完了がT[i]以前でないとその辺は移動できない)

1番の頂点から始め、全頂点を1回ずつたどってもとに戻る最短時間を求めよ。

解法

dp[現在の頂点][通過済み頂点] := 条件を満たす最短移動時間
としてダイクストラをやるだけ。
D,Tが無駄に大きいのでintを使わないよう注意。

int N,M;
vector<pair<int,pair<ll,ll>>> E[50];

ll dist[16][1<<16];
ll num[16][1<<16];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	if(N==1) return _P("0 1\n");
	FOR(i,M) {
		ll d,t;
		cin>>x>>y>>d>>t;
		E[x-1].push_back({y-1,{d,t}});
		E[y-1].push_back({x-1,{d,t}});
	}
	memset(dist,0x3f,sizeof(dist));
	dist[0][0]=0;
	num[0][0]=1;
	priority_queue<pair<ll,int> > Q;
	Q.push({0,0});
	
	while(Q.size()) {
		auto r=Q.top();
		Q.pop();
		ll co=-r.first;
		int cur=r.second % 100;
		int mask=r.second / 100;
		if(co!=dist[cur][mask]) continue;
		
		FORR(e,E[cur]) {
			int tar=e.first;
			if(mask&(1<<tar)) continue;
			ll co2=co+e.second.first;
			if(co2>e.second.second) continue;
			if(co2<dist[tar][mask|(1<<tar)]) {
				num[tar][mask|(1<<tar)] = 0;
				dist[tar][mask|(1<<tar)]=co2;
				Q.push({-co2,(mask|(1<<tar))*100+tar});
			}
			if(co2==dist[tar][mask|(1<<tar)]) num[tar][mask|(1<<tar)] += num[cur][mask];
		}
		
	}
	
	if(num[0][(1<<N)-1]==0) return _P("IMPOSSIBLE\n");
	_P("%lld %lld\n",dist[0][(1<<N)-1],num[0][(1<<N)-1]);
	
}

まとめ

これD,Tがこんな大きい必要あったのかな…。