Submission #681207

#	Time	Username	Problem	Language	Result	Execution time	Memory
681207		Ninja_Kunai	Relay Marathon (NOI20_relaymarathon)	C++14	100 / 100	1884 ms	97072 KiB

RelayMarathon

/**
*    Author :  Nguyen Tuan Vu
*    Created : 12.01.2023
**/

#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define MASK(x) ((1ll)<<(x))
#define BIT(x, i) (((x)>>(i))&(1))
#define ALL(v)  (v).begin(), (v).end()
#define REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define FOR(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i)
#define db(val) "["#val" = "<<(val)<<"] "
#define TIME  (1.0 * clock() / CLOCKS_PER_SEC)

template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}

using namespace std;

mt19937 jdg(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r) {return l + jdg() % (r - l + 1);}

void file(){
    #define TASK "TASK"
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }
}

const int N = 1e5 + 5;
const int INF = 1e9 + 7;
int n, m, K, head[N], dist[N], MIN[2][4], dist2[N];
vector <pair <int, int>> adj[N];
vector <int> Spe, new_Spe;

void dijkstra(vector <int> Spe) {
	FOR(i, 1, n) dist[i] = INF;
	priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> heap;
	for (auto x : Spe) {
		head[x] = x;
		heap.push({dist[x] = 0, x});
	}

	while (heap.size()) {
		int du = heap.top().first;
		int u = heap.top().second;

		heap.pop();
		if (du != dist[u]) continue;
		for (auto v : adj[u]) if (minimize(dist[v.second], dist[u] + v.first)) {
			heap.push({dist[v.second], v.second});
			head[v.second] = head[u];
		}
	}
}

int shortest_path(vector <int> Spe) {
    dijkstra(Spe);
    int D = INF;

    FOR(u, 1, n) for (auto x : adj[u]) {
    	int v = x.second;
    	if (head[v] != head[u]) {
            minimize(D, dist[v] + dist[u] + x.first);
    	}
    }

    return D;
}

void dijkstra2(int x, int MIN[], int dist[]) {
	FOR(i, 1, n) dist[i] = INF;
	priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> heap;
	heap.push({dist[x] = 0, x});

	while (heap.size()) {
		int du = heap.top().first;
		int u = heap.top().second;

		heap.pop();
		if (du != dist[u]) continue;
		for (auto v : adj[u]) if (minimize(dist[v.second], dist[u] + v.first)) {
			heap.push({dist[v.second], v.second});
			head[v.second] = head[u];
		}
	}

	MIN[0] = MIN[1] = MIN[2] = INF;
	for (auto z : Spe) if (z != x) {
        if (dist[z] < MIN[0]) {
            MIN[3] = MIN[2];
            MIN[2] = MIN[1];
            MIN[1] = MIN[0];
            MIN[0] = dist[z];
        }
        else if (dist[z] < MIN[1]) {
            MIN[3] = MIN[2];
            MIN[2] = MIN[1];
            MIN[1] = dist[z];
        }
        else if (dist[z] < MIN[2]) {
            MIN[3] = MIN[2];
            MIN[2] = dist[z];
        }
        else minimize(MIN[3], dist[z]);
	}
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    file();
    cin >> n >> m >> K;
    FOR(i, 1, m) {
    	int u, v, w; cin >> u >> v >> w;
    	adj[u].push_back({w, v});
    	adj[v].push_back({w, u});
    }

    FOR(i, 1, K) {
    	int x; cin >> x;
    	Spe.push_back(x);
    }

    dijkstra(Spe);
    int A = 0, B = 0, D = INF;

    FOR(u, 1, n) for (auto x : adj[u]) {
    	int v = x.second;
    	if (head[v] != head[u] && minimize(D, dist[v] + dist[u] + x.first)) {
    		A = head[u];
    		B = head[v];
    	}
    }

    //cout << A << ' ' << B << '\n';
    for (auto x : Spe) if (x != A && x != B) new_Spe.push_back(x);
    int res = 2 * INF;
	minimize(res, shortest_path(Spe) + shortest_path(new_Spe));
	dijkstra2(A, MIN[0], dist);
	dijkstra2(B, MIN[1], dist2);

	for (auto x : Spe) if (x != A && x != B) {
        int cost = dist2[x];
        int bonus = 0;

        if (MIN[0][0] == dist[x] || MIN[0][0] == dist[A] || MIN[0][0] == dist[B]) {
            if (MIN[0][1] == dist[x] || MIN[0][1] == dist[A] || MIN[0][1] == dist[B]) {
                if (MIN[0][2] == dist[x] || MIN[0][2] == dist[A] || MIN[0][2] == dist[B]) {
                    bonus = MIN[0][3];
                }
                else bonus = MIN[0][2];
            }
            else bonus = MIN[0][1];
        }
        else bonus = MIN[0][0];

        minimize(res, cost + bonus);
	}

	cout << res;
    cerr << "Time elapsed: " << TIME << " s.\n";
    return 0;
}

/*
==================================================+
INPUT:                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

Compilation message (stderr)

RelayMarathon.cpp: In function 'void file()':
RelayMarathon.cpp:35:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
RelayMarathon.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 12 / 12
• Subtask 3: 25 / 25
• Subtask 4: 58 / 58