CF1503C Travelling Salesman Problem

wflengxuenong · 2022-11-08 09:55:25 · 个人记录

从1号出发，回到1号，假设为1342所走路径为13，34，42，21，移动个顺序为3421，所走路径为一样的，所以出发点无差别。

i->j花费max(ci,aj-ai)，也就是max(0,aj-ai-ci)+ci

每个ci必需花费，也就是max(0,aj-ai-ci),当aj<=ai+ci时候可以花费小.如何安排可以让汉密尔顿回路权值最小？

按照a从小到大排序后，从大数走到小数时候权值一定为0。我们求从1到n的最短路，然后从n到1，将没走过的点逆序走一遍权值为0

因此转化为求从1到n的最短路。如何建图呢？

任意i>j那么从i到j到的权值为0 .i+1-i权值为0，从i到j(i<j)如何建边呢？ 对每个i，找出前面最接近的ai+ci的aj连边，aj<ai+ci连0边，j+1连接对应权值的边。。 
0，0 1 ：1
1，2 3：5
2，3 0：3
3，4 2：6
4，7 1：8
5，8 4：12 

0号到1号连w=1的边
1号到2号w=0
1号到3号w=1，连解更大的权值更大，不会先更新到。没必要去连接更大的边。 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+9; 

vector<pair<ll,ll> >city; 
int main() {
    int n;
    cin >> n;
    ll ans = 0;
    for(int i = 0; i < n; i++) {
        ll a, c;
        cin >> a >> c;
        city.push_back({a, c});
        ans += c;
    }
    sort(city.begin(), city.end());//按照a排序 
    priority_queue<pair<ll, int> > Q;//-值入 
    vector<bool>vis(n, false);
    Q.push({0, 0});
    while(!Q.empty()) {//dijstrla
        //std::tie会将变量的引用整合成一个tuple，从而实现批量赋值。tuple,pair的扩展。 
        ll d; int i;
        tie(d, i) = Q.top(); Q.pop();
        if(vis[i]) continue;
        vis[i] = true;
        if(i == n - 1) {
            ans-= d;
            break;
        }
        if(i > 0) {
            Q.push({d, i - 1});
        }
        int j = lower_bound(city.begin(), city.end(), make_pair(city[i].first + city[i].second, LLONG_MAX)) - city.begin() - 1;
        Q.push({d, j});//找到第一小于，连0权边。 
        if(j + 1 < n) {
            Q.push({d - city[j + 1].first + city[i].first + city[i].second, j + 1});
            // -（-d+ aj-（ai+ci）） 
        }

    }
    cout << ans << '\n';
}