Submission #1164314

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164314		icebear	Relay Marathon (NOI20_relaymarathon)	C++20	100 / 100	1165 ms	81264 KiB

RelayMarathon

// ~~ icebear love attttt ~~
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;

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

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

#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORR(i,a,b) for(int i=(a); i>=(b); --i)
#define REP(i, n) for(int i=0; i<(n); ++i)
#define RED(i, n) for(int i=(n)-1; i>=0; --i)
#define MASK(i) (1LL << (i))
#define BIT(S, i) (((S) >> (i)) & 1)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define task "icebearat"

const int MOD = 1e9 + 7;
const int inf = 1e9 + 27092008;
const ll INF = 1e18 + 27092008;
const int N = 1e5 + 5;
int n, m, k;
map<int, int> dist[N];
vector<ii> G[N];
struct state {
    int root, node, dist;
    bool operator < (const state &other) const {
        return dist > other.dist;
    }
};
priority_queue<state> Q;
vector<state> distances;
bool special[N];

void init(void) {
    cin >> n >> m >> k;
    FOR(i, 1, m) {
        int u, v, w;
        cin >> u >> v >> w;
        G[u].pb(mp(v, w));
        G[v].pb(mp(u, w));
    }
    FOR(i, 1, k) {
        int x; cin >> x;
        special[x] = true;
        Q.push({x, x, 0});
        dist[x][x] = 0;
    }
}

void process(void) {
    ll ans = INF;
    while(!Q.empty()) {
        auto x = Q.top(); Q.pop();
        if (dist[x.root][x.node] != x.dist) continue;
        if (x.dist > ans) break;
        for(ii t : G[x.node]) {
            int v, w; tie(v, w) = t;
            if (x.dist + w > ans) continue;
            if (dist[x.root].find(v) == dist[x.root].end() || dist[x.root][v] > x.dist + w) {
                int &tmp = dist[x.root][v];
                tmp = x.dist + w;
                Q.push({x.root, v, tmp});
                if (special[v]) {
                    for(auto p : distances)
                        if (p.root != x.root && p.root != v && p.node != x.root && p.node != v)
                            minimize(ans, (ll)p.dist + tmp);
                    distances.pb({x.root, v, tmp});
                }
            }
        }
    }
    cout << ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    int tc = 1;
//    cin >> tc;
    while(tc--) {
        init();
        process();
    }
    return 0;
}

Compilation message (stderr)

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

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