D. Maximum Distance

1800 MST
  • Quiz
  • AC
  • 問題理解
    • 最初、max, min, cost, distanceで混乱した
    • costについては「経路上の1番高いコストの切符を買えば、他は無料」と考える
    • speciall vertexについては「見所」と考える。各見所から他の見所の全てに行きたい時、いくら持っていればいいか。それをspecial vertext各点について求める
  • 解説
    • MSTを作る
    • MSTに採用された各辺について、頂点A側、頂点B側のそれぞれにspecial vertexがあるなら、その辺は答えの対象になる
  • 解説2
    • MSTを作る時は辺コストが低い順に採用していくが、採用してUnionFindでいうuniteした時に、グループごとのspecial vertexの数も統合することにする（各グループの根に集めるとする）
    • uniteを続けるといずれspecial vertexの数 == Kとなり、その時の辺のコストが答え
struct Edge{
    ll from;
    ll to;
    ll cost;
    Edge(ll from, ll to, ll cost): from(from), to(to), cost(cost) {}
    bool operator<(const Edge &another) const
    {
        return cost < another.cost;
    }
    bool operator>(const Edge &another) const
    {
        return cost > another.cost;
    }
};

struct UnionFind{
    vector<ll> parent;
    UnionFind(ll sz){
        parent.resize(sz);
        reset();
    }

    void reset(){
        FOR(i, 0, parent.size()){
            parent[i] = i;
        }
    }

    void unite(ll a, ll b){
        if(a>b){
            swap(a, b);
        }
        ll rootA = findRoot(a);
        ll rootB = findRoot(b);
        if(rootA>rootB){
            swap(rootA, rootB);
        }
        if(rootA==rootB){
            return;
        }else{
            // 小さい方を親にする
            parent[rootB] = rootA;
        }
    }

    ll findRoot(ll a){
        if(parent[a]==a){
            return a;
        }else{
            return parent[a] = findRoot(parent[a]);
        }
    }

    map<ll, vector<ll> > getGroups(){
        map<ll, vector<ll> > G;
        FOR(i, 0, parent.size()){
            ll r = findRoot(i);
            G[r].push_back(i);
        }
        return G;
    }

    bool is_same_group(ll a, ll b){
        ll rootA = findRoot(a);
        ll rootB = findRoot(b);
        if(rootA==rootB){
            return true;
        }else{
            return false;
        }
    }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N,M,K;
    cin>>N>>M>>K;

    // special
    VI X(K);
    rep(i,K){
      cin>>X[i];
      X[i]--;
    }

    // コストの小さい順に取り出す設定
    priority_queue<Edge, vector<Edge>, greater<Edge> > que;
    
    // edge
    rep(i,M){
      ll a,b,c;
      cin>>a>>b>>c;
      a--;b--;
      que.push(Edge(a,b,c));
    }

    UnionFind uf(N);
    
    // special vertex count (mergeする)
    VI C(N);
    for(ll x : X) C[x]=1;
    debug(C);

    // MST
    while(!que.empty()){
      auto edge = que.top(); que.pop();

      ll fr = edge.from;
      ll to = edge.to;

      if(!uf.is_same_group(fr, to)){
        ll r0 = uf.findRoot(fr);
        ll r1 = uf.findRoot(to);

        uf.unite(fr, to);

        ll r2 = uf.findRoot(fr);

        if(r0==r2){
          C[r2] += C[r1];
          C[r1]=0;
        }else{
          C[r2] += C[r0];
          C[r0]=0;
        }

        if(C[r2]==K){
          VI Ans;
          rep(i,K) Ans.push_back(edge.cost);
          print_vector(Ans);
          return 0;
        }
      }
    }
    p(-1);
    
    return 0;
}