Submission #746007

#	Time	Username	Problem	Language	Result	Execution time	Memory
746007		vjudge1	Cities (BOI16_cities)	C++17	0 / 100	268 ms	22392 KiB

cities

#include <bits/stdc++.h>
using namespace std;
#define InTheNameOfGod ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
using ll = long long;

const ll maxN = 2e5 + 5;
const ll MOD = 1e9 + 7;
const ll INF = 1e9 + 7;

ll n,k,m;

ll sum = 0;

vector<vector<pair<ll, ll> > > g;

struct Node {
    ll dist, x, p, w;
};

bool operator< (const Node &a,const Node &b) {
    return a.dist > b.dist;
}

bool operator> (const Node &a, const Node &b) {
    return a.dist < b.dist;
}

set<pair<ll, pair<ll, ll> > > s;
vector<ll> d;

vector<pair<ll, ll> > p;
void dijkstra(ll start) {
    priority_queue<Node> pq; 
    pq.push({0, start, start, 0});

    p.assign(n+1, {-1, -1});
    d.assign(n+1, -1);
    while(!pq.empty()) {
        Node cur = pq.top();
        pq.pop();

        if(d[cur.x] != -1) continue;
        p[cur.x] = {cur.p, cur.w};
        d[cur.x] = cur.dist;

        for(pair<ll, ll> sz : g[cur.x]) {
            if(d[sz.first] != -1) continue;

            pq.push({cur.dist + sz.second, sz.first, cur.x, sz.second});
        }
    }
}

void visszafejt(ll eleje, ll vege) {
    ll cur = eleje;
    while(cur != vege) {
        ll next = p[cur].first, w = p[cur].second;

        if(cur < next) {
            if(s.find({w,{cur,next}}) != s.end()) {
                s.erase({w,{cur,next}});
                sum += w;
            }
            else s.insert({w,{cur,next}});
        }
        else {
            if(s.find({w,{next,cur}}) != s.end()) {
                s.erase({w,{next,cur}});
                sum += w;
            }
            else s.insert({w,{next,cur}});
        }
        cur = next;
    }
}

int main() {

/*#ifndef ONLINE_JUDGE
   freopen("../../input.txt", "r", stdin);
   freopen("../../output.txt", "w", stdout);
#endif*/
   InTheNameOfGod;

    cin >>n >>k >> m;

    vector<ll> fontos(k);
    for(ll &i : fontos) cin >> i;

    g.resize(n+1);
    for(ll i = 0; i < m; i++) {
        ll x,y,z;
        cin >> x >> y >> z;
        g[x].push_back({y, z});
        g[y].push_back({x, z});
    }



    dijkstra(fontos[0]);

    if(k == 2) {
        cout << d[fontos[1]];
        return 0;
    }
    visszafejt(fontos[1], fontos[0]);
    /*for(auto i : s) {
        cout << i.first << " " << i.second.first << " " << i.second.second << endl;
    }
    cout << endl;*/
    visszafejt(fontos[2], fontos[0]);
    /*for(auto i : s) {
        cout << i.first << " " << i.second.first << " " << i.second.second << endl;
    }
    cout << endl;*/
    dijkstra(fontos[1]);
    visszafejt(fontos[2], fontos[1]);
    /*for(auto i : s) {
        cout << i.first << " " << i.second.first << " " << i.second.second << endl;
    }
    cout << endl;*/

    ll maxi = 0;
    for(auto i : s) {
        sum += i.first;
        maxi = max(maxi, i.first);
    }

    cout << sum - maxi;

    return 0;
}

• Subtask 1: 0 / 22
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 26