Submission #1163936

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163936		dwuy	Relay Marathon (NOI20_relaymarathon)	C++20	25 / 100	1447 ms	424264 KiB

RelayMarathon

/**         - dwuy -

　　　　　 ／＞　   フ
　　　　　 | 　_　 _|
　 　　　 ／`ミ _x ノ
　　 　 /　　　 　 |
　　　 /　  ヽ　　 ?
　／￣|　　 |　|　|
　| (￣ヽ＿_ヽ_)_)
　＼二つ

**/
#include <bits/stdc++.h>

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) (int)((s).size())
#define MASK(k)(1LL<<(k))
#define TASK "test"
#define int long long

using namespace std;

typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;

const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MX = 100005;

int n, m, k;
vector<pii> G[MX];
map<int, int> d[MX];
bitset<MX> khiep = 0;

int32_t main(){
    fastIO;
    //file(TASK);

    cin >> n >> m >> k;
    for(int i=1; i<=m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }
    priority_queue<tpiii, vector<tpiii>, greater<tpiii>> Q;
    for(int i=1; i<=k; i++){
        int x; cin >> x;
        khiep[x] = 1;
        d[x][x] = 0;
        Q.push({0, x, x});
    }
    vector<pair<int, pii>> gg;
    int ans = 1e18;
    while(Q.size()){
        int du, r, u;
        tie(du, r, u) = Q.top();
        Q.pop();
        if(du != d[r][u]) continue;
        if(u != r && khiep[u]){
            // cerr << u << ' ' << r << endl;
            for(int i=0; i<len(gg); i++){
                int x, y; tie(x, y) = gg[i].se;
                if(x != r && x != u && y != r && y != u){
                    cout << gg[i].fi + du << endl;
                    // ans = min(ans, gg[i].fi + du);
                    return 0;
                }
            }
            gg.push_back({du, {r, u}});
        }

        for(pii e: G[u]){
            int v, c; tie(v, c) = e;
            auto itr = d[r].find(v);
            if(itr != d[r].end() && d[r][v] <= du + c) continue;
            d[r][v] = du + c;
            Q.push({du + c, r, v});
        }
    }

    cerr << ans << endl;

    return 0;
}

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