Submission #1163958

#TimeUsernameProblemLanguageResultExecution timeMemory
1163958dwuyRelay Marathon (NOI20_relaymarathon)C++20
0 / 100
3297 ms100444 KiB
/**         - 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;

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...