Submission #336735

#	Time	Username	Problem	Language	Result	Execution time	Memory
336735		camnguyenmeow	Relay Marathon (NOI20_relaymarathon)	C++14	0 / 100	1782 ms	212216 KiB

RelayMarathon

#include <bits/stdc++.h>
using namespace std;
#define ll long
#define pii pair<int,long>
#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 d[100005], c[5001][5001];
bool sp[100005], vis[100005];
vector<pii> adj[100005];
int main()
{
    camnguyenmeow;
    cin >> n >> m >> k;
    vector<pair<pii, int> > dsc(m);
    int x, y;
    ll z;
    bool sub3 = true;
    for (pair<pii, int> &i : dsc) {
        cin >> i.fr.fr >> i.fr.sc >> i.sc;
        if ((i.fr.fr == 1 && i.fr.sc != 2) || (i.fr.fr == 2 && i.fr.sc != 1) || (i.fr.fr != 1 && i.fr.sc == 2) || (i.fr.fr != 2 && i.fr.sc == 1)) sub3 = false;
        if (((i.fr.fr == 1 && i.fr.sc == 2) || (i.fr.fr == 2 && i.fr.sc == 1)) && i.sc != 1) sub3 = false;
        adj[i.fr.fr].push_back({i.fr.sc, i.sc}); adj[i.fr.sc].push_back({i.fr.fr, i.sc});
    }
    FOR(i, 1, k) {
        cin >> a[i]; sp[a[i]] = true;
    }
    if (sub3) {
        ll ans = LONG_MAX;
        FOR(i, 3, k) {
            priority_queue<pii, vector<pii>, greater<pii> > pq;
            memset(d, 0x3f, sizeof(d));
            memset(vis, 0, sizeof(vis));
            vis[1] = vis[2] = true;
            d[a[i]] = 0;
            pq.push({0, a[i]});
            int cnt = 0;
            while (!pq.empty()) {
                int u = pq.top().sc; pq.pop();
                if (vis[u]) continue;
                vis[u] = true;
                if (sp[u]) ++cnt;
                if (d[u] > ans) break;
                if (cnt == 2) {
                    ans = min(ans, d[u]);
                    break;
                }
                for (pii v : adj[u])
                    if (!vis[v.fr] && d[v.fr] > d[u] + v.sc) {
                        d[v.fr] = d[u] + v.sc;
                        pq.push({d[v.fr], v.fr});
                    }
            }
        }
        cout << ans + 1;
        return 0;
    }
    memset(c, 0x3f, sizeof(c));
    for (pair<pii, int> i : dsc)
        c[i.fr.fr][i.fr.sc] = c[i.fr.sc][i.fr.fr] = i.sc;
    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;
}

Compilation message (stderr)

RelayMarathon.cpp: In function 'int main()':
RelayMarathon.cpp:60:9: warning: unused variable 'x' [-Wunused-variable]
   60 |     int x, y;
      |         ^
RelayMarathon.cpp:60:12: warning: unused variable 'y' [-Wunused-variable]
   60 |     int x, y;
      |            ^
RelayMarathon.cpp:61:8: warning: unused variable 'z' [-Wunused-variable]
   61 |     ll z;
      |        ^

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