Submission #336725

#	Time	Username	Problem	Language	Result	Execution time	Memory
336725		camnguyenmeow	Relay Marathon (NOI20_relaymarathon)	C++14	17 / 100	777 ms	384628 KiB

RelayMarathon

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define fr first
#define sc second
#define pow2(i) (1<<i)
#define eb emplace_back
#define mp make_pair
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define FOR(_i, _s, _n) 	for (int _i = _s; _i <= _n; ++_i)
#define FOD(_i, _s, _n)	    for (int _i = _s; _i >= _n; --_i)
#define firstbit(_mask)     __builtin_ctz(_mask)
#define lastbit(_mask)      __builtin_clz(_mask)
#define countbit(_mask)     __builtin_popcount(_mask)
int getbit(int mask, int i) {
    return (mask >> i) & 1;
}
void flipbit(int &mask, int i) {
    mask ^= (1 << i);
}
void setbit(int &mask, int i) {
    mask |= (1 << i);
}
template <typename T> inline void read(T &x) {
    x = 0; char c;
    while (!isdigit(c = getchar()));
    do x = x*10 + c - '0';
    while (isdigit(c = getchar()));
}
template <typename T> inline void write(T x) {
    if (x > 9) write(x/10);
    putchar(x % 10 + 48);
}
const int dd[4]={-1, 0, 1, 0}, dc[4]={0, 1, 0, -1};
//#define PROBLEMS            "RELAYMARATHON"
#ifdef PROBLEMS
    #define cin fi
    #define cout fo
    ifstream fi (PROBLEMS".inp");
    ofstream fo (PROBLEMS".out");
#endif
#define camnguyenmeow ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
/*   /\_/\
    (= ._.)
    / >?  \>$
*/
int n, m, k, firstnear[5001], secondnear[5001], a[5001];
ll c[5001][5001];
bool sp[5001];
int main()
{
    camnguyenmeow;
    memset(c, 0x3f, sizeof(c));
    cin >> n >> m >> k;
    int x, y;
    ll z;
    FOR(i, 1, m) {
        cin >> x >> y >> z;
        c[x][y] = c[y][x] = z;
    }
    FOR(i, 1, k) {
        cin >> a[i];
        sp[a[i]] = true;
    }
    FOR(i, 1, n)
        FOR(u, 1, n)
            FOR(v, 1, n) {
                c[u][v] = min(c[u][v], c[u][i] + c[i][v]);
                if (sp[v] && sp[u] && v != u) {
                    if (c[u][firstnear[u]] > c[u][v]) {
                        secondnear[u] = firstnear[u];
                        firstnear[u] = v;
                    }
                    else if (v != firstnear[u] && c[u][secondnear[u]] > c[u][v])
                        secondnear[u] = v;
                }
            }
    ll ans = LONG_MAX;
    FOR(i, 1, k)
        FOR(j, 1, k) {
            if (i == j) continue;
            int fn = firstnear[a[j]], sn = secondnear[a[j]];
            FOR(z, 1, k) {
                if (z == i || z == j) continue;
                if (fn && fn != a[i] && fn != a[z])
                    ans = min(ans, c[a[i]][a[z]] + c[a[j]][fn]);
                else if (sn && sn != a[i] && sn != a[z])
                    ans = min(ans, c[a[i]][a[z]] + c[a[j]][sn]);
            }
        }
    cout << ans;
}

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