yukicoder : No.1480 Many Complete Graphs

想定解と違う解法だった。
https://yukicoder.me/problems/no/1480

問題

N点のグラフを考える。
頂点集合とパラメータC[i]の対がM個与えられるので、以下のように辺を張る。

• 集合内の頂点対x,yに対し、ceil((x+y)/2)+C[i]のコストの無向辺を張る

1番の頂点からN番の頂点に至る対象コストを求めよ。

解法

コストを倍にして考え、最後に2で割ることを考える。
各集合・パラメータ対C[i]に対し、以下のように辺を張ろう。

• 超頂点V[i]を1個作り、集合内の点uとの間に、コスト(u+C[i])の辺を張る

これでダイクストラ法を行うわけだが、これだとceilの効果が反映されない。
そこで、(超頂点を除く)元のN点については、常にコストが偶数となるようround upするルールを加えるとよい。

int N,M;
vector<pair<int,int>> E[201010];
ll D[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>k>>x;
		FOR(j,k) {
			cin>>y;
			E[y].push_back({i+N+1,x+y});
			E[i+N+1].push_back({y,x+y});
		}
	}
	FOR(i,202020) D[i]=1LL<<60;
	D[1]=0;
	priority_queue<pair<ll,int>> Q;
	Q.push({0,1});
	while(Q.size()) {
		ll co=-Q.top().first;
		int cur=Q.top().second;
		Q.pop();
		if(D[cur]!=co) continue;
		if(cur<=N && co%2) co++;
		
		if(cur==N) {
			cout<<co/2<<endl;
			return;
		}
		
		FORR2(e,c,E[cur]) if(D[e]>co+c) {
			D[e]=co+c;
			Q.push({-D[e],e});
		}
		
		
	}
	cout<<-1<<endl;
}

まとめ

さっと思いつけて良かった。