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がこんな大きい必要あったのかな…。