Codeforces #712 Div1 : C. Travelling Salesman Problem

ちょっと問題名いじるといいのにね。
https://codeforces.com/contest/1503/problem/C

問題

N頂点の完全グラフを考える。
各頂点vには(A[v],C[v])の2つのパラメータが設定されている。
頂点i→jに遷移するコストは、max(C[i],A[j]-A[i])である。
全頂点を1回ずつ訪問する閉路の最小コストを求めよ。

解法

最低でもsum(C)分コストがかかるのはわかる。
あとは、A[j]-A[i]が小さくなるような訪問順を考えよう。

コストC[i]で移動する場合に比べ、コストA[j]-A[i]で移動する場合の方が悪いケースは、A[j]-A[i]-C[i]=A[j]-(A[i]+C[i])が正の場合である。
A[i]の小さい順に頂点を見て、(A[i]+C[i])の最大値Bを記録しよう。頂点jに到達する場合、コストは(C[j]+max(0,A[j]-B))となる。

int N;
int A[101010],C[101010];
pair<int,int> P[101010];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	ll ret=0;
	FOR(i,N) {
		cin>>A[i]>>C[i];
		P[i]={A[i],i};
		ret+=C[i];
	}
	
	sort(P,P+N);
	int cur=A[P[0].second]+C[P[0].second];
	for(i=1;i<N;i++) {
		x=P[i].second;
		if(A[x]>cur) ret+=A[x]-cur;
		cur=max(cur,A[x]+C[x]);
	}
	
	cout<<ret<<endl;
	
}

まとめ

コードは短いけど、本番結構考察にてこずってる。