CF712 Div2 E Traveling Salesman Problem

内容

• CodeForces 712 Div2 E問題を、pythonでといた

  問題

codeforces.com

考えたこと

• TSPだけど、N<=10*5なので、greedyとかで行けそう。
• beautyが大きいところから、小さいところには、cでいける。
  • 一番beautyが大きい都市まで行けば、あとは、残りを辿るだけで良くなる。

ポイント

• どんな移動をしても、最低で C=sum(c_i)はかかる。
• max_beautyの都市まで行けば、あとは c_iだけの移動になる。
• city1-> max_beauty_city間での、最短路を求めればいい。

実装

N = int(input())
costs=[list(map(int,input().split())) for _ in range(N)]

# beautyでsortする。
costs=[(a,a+b) for a,b in costs]
costs = sorted(costs,key=lambda x:x[0])

#とりあえず。costのsumは絶対必要。(それをどれだけ増やさずにいけるか)
min_ans=sum(v[1]-v[0] for v in costs)

#i->jの移動コストは、 ci + max(0,aj-ai-ci))
#ciは先に足してあるので、max(0,aj-ai-ci)を小さくする。

#今まで使った(ai+ci)の最大値を記録しておく。そこからの差分だけ増やしていけばいい
dist=costs[0][0]

print("sort=>",costs)
#とりあえず、 max_beautyの都市まで行けばいい。
for i in range(N):
    min_ans += max(0,costs[i][0]-dist)
    dist = max(dist,costs[i][1])

print(min_ans)

#終わりに
* atcoderのどこかにも、似た問題があった気がした。
思い出せないけど・