Submission #1301422

#TimeUsernameProblemLanguageResultExecution timeMemory
1301422chaitanyamehtaRelay Marathon (NOI20_relaymarathon)C++20
0 / 100
27 ms11016 KiB
#include<bits/stdc++.h>
using namespace std;

#define int long long
vector<int> s , vis;

struct Edge{
    int v , c;
};
vector<vector<Edge>> g , a;

void dfs(int u , int c , int spl){
    if(u != spl){
        if(s[u]) {
            a[spl].push_back({u , c});
            // a[u].push_back({spl , c});
            spl = u;
            c = 0;
        } 
    }
    vis[u] = 1;
    for(auto v : g[u]){
        if(!vis[v.v]){
            dfs(v.v , c + v.c , spl);
        }
    }
}

signed main(){
    ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);
    int n , m , k;
    cin>>n>>m>>k;
    g.resize(n+1);
    a.resize(n+1);
    vis.resize(n+1);
    for(int i = 0 ;i < m; i++){
        int u , v , c;
        cin>>u>>v >> c;
        g[u].push_back({v, c});
        g[v].push_back({u , c});
    }
    
    s.resize(n+1);
    for(int i = 0 ;i < k ;i++){
        int u;cin>>u;s[u]=1;
    }
    for(int i = 1 ; i <= n ;i++){
        if(!vis[i] && s[i]){
            dfs(i , 0 , i);
        }
    }
    vector<int> o;
    for(int i = 0 ;i < a.size() ; i++){
        for(int j = 0 ; j< a[i].size() ; j++){
            o.push_back(a[i][j].c);
            // cout<< o.back() << " ";
        }
    }
    sort(o.begin() , o.end());
    cout<<o[0] + o[1];

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...