Submission #336316

#	Time	Username	Problem	Language	Result	Execution time	Memory
336316		camnguyenmeow	Relay Marathon (NOI20_relaymarathon)	C++14	0 / 100	369 ms	397164 KiB

RelayMarathon

#include <bits/stdc++.h>
using namespace std;
#define ll 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] && v != firstnear[u]) {
                    if (c[u][firstnear[u]] > c[u][v]) {
                        secondnear[u] = firstnear[u];
                        firstnear[u] = v;
                    } else if (c[u][secondnear[u]] > c[u][v])
                        secondnear[u] = v;
                }
            }
    auto check = [&] (int i, int j, int k, int l) {
        if (i == j || i == k || i == l || j == k || j == l || k == l) return false;
        return true;
    };
    ll ans = INT_MAX;
    FOR(i, 1, k)
        FOR(j, 1, k) {
            if (i == j) continue;
            int a1 = a[i], b1 = a[j], d1, d2;
            d1 = firstnear[b1], d2 = secondnear[b1];
            if (check(a1, b1, d1, d2))
                ans = min(ans, c[a1][d1] + c[b1][d2]);
            FOR(z, 1, k) {
                int a2 = a[z];
                if (check(a1, a2, b1, d1))
                    ans = min(ans, c[a1][a2] + c[b1][d1]);
            }
        }
    cout << ans;
}

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