Cities

Drzewo Steinera

Nietrudno się przekonać, że taki podgraf musi być drzewem (bo w przeciwnym wypadku możemy z niego usunąć krawędź leżącą na cyklu, nie psując spójności i zmniejszając wagę podgrafu). Drzewo to nazywa się w teorii grafów drzewem Steinera.

Jest to klasyczny problem, który w ogólności jest NP-zupełny, ale dla małych wartości $k$ wykładnicze algorytmy radzą sobie całkiem dobrze. W szczególności dla ograniczenia $k\leq 5$ z zadania można zaproponować całkiem prosty algorytm.

Jeśli zaznaczymy sobie w grafie drzewo Steinera, usuniemy wszystkie krawędzie do niego nienależące i scalimy niewyróżnione wierzchołki stopnia 2, to dostaniemy taki obrazek:

 1---*---*---*---5
    /    |    \
 2-/     3     \-4

Wierzchołki wyróżnione są w nim połączone ścieżkami z co najwyżej $k-2$ wierzchołkami „pomocniczymi”. Łatwo pokazać, że wierzchołki pomocnicze leżą na jednej ścieżce $p$ (zauważmy, że to nie musi być prawdą już dla $k=6$), a wszystkie pozostałe łączą się z $p$ za pomocą pojedynczych ścieżek.

Długości tych pojedynczych ścieżek łatwo znaleźć, uruchamiając algorytm Dijkstry z każdego wierzchołka wyróżnionego. To zajmie czas $O(k m \log n)$.

Pomysł jest więc taki, żeby przejść po ścieżce $p$, przy okazji „podczepiając” do niej wierzchołki wyróżnione. Będziemy iść po wirtualnym grafie, którego wierzchołki są postaci $(v,mask)$, gdzie $v$ jest wierzchołkiem oryginalego grafu, a $mask \in [0, 2^k)$ jest maską bitową, która opisuje, które wierzchołki wyróżnione już podłączyliśmy.

Na tym wirtualnym grafie też uruchamiamy algorytm Dijkstry. Zaczynamy od wszystkich wierzchołków postaci $(v,0)$, a chcemy dojść do dowolnego postaci $(v,2^k-1)$.

Krawędzie z wierzchołka $(v,mask)$ są dwojakiego rodzaju. Prowadzą do $(w,mask)$ z kosztem $c$, jeśli mieliśmy krawędź z $v$ do $w$ o koszcie $c$ w oryginalnym grafie (to odpowiada przejściu po ścieżce $p$). Lub też do $(v,mask+2^i)$ o koszcie $dist(v,i)$, jeśli $i$ jest niewybranym wierzchołkiem wyróżnionym (to odpowiada podłączeniu wierzchołka $i$). Złożoność wynosić będzie $O( (nk+m)2^k \log (n2^k) )$.

const int N = 210000, K = 5;
int n,k,m,city[K];
vector<pli> adj[N];
vector<ll> dist[K];

vector<ll> dijkstra(int n, vector<int> s, function<vector<pli>(int)> adj) {
  vector<ll> dist(n, 1e18);
  priority_queue<pli,vector<pli>,greater<pli>> q;
  for (int v : s) {
    dist[v] = 0;
    q.push(make_pair(0,v));
  }
  while (!q.empty()) {
    auto [d, v] = q.top(); q.pop();
    if (dist[v] < d) continue;
    vector<pli> edges = adj(v);
    for (auto [cost, u] : edges) {
      if (dist[v] + cost < dist[u]) {
        dist[u] = dist[v] + cost;
        q.push(make_pair(dist[u], u));
      }
    }
  }
  return dist;
}

int main() {
  scanf("%d%d%d",&n,&k,&m);
  REP(i,k) {
    scanf("%d",&city[i]);
    --city[i];
  }
  REP(i,m) {
    int a,b,c; scanf("%d%d%d",&a,&b,&c);
    --a; --b;
    adj[a].emplace_back(ll(c), b);
    adj[b].emplace_back(ll(c), a);
  }

  REP(i,k) {
    dist[i] = dijkstra(n, { city[i] }, [](int v) { return adj[v]; });
  }

  auto graph_adj = [](int v) {
    int w = v%n, mask = v/n;
    vector<pli> ans;
    for (auto [cost, u] : adj[w]) {
      ans.emplace_back(cost, u + mask*n);
    }
    REP(i,k) if (!(mask & 1<<i)) {
      ans.emplace_back(dist[i][w], w + (mask | (1<<i))*n);
    }
    return ans;
  };

  vector<int> s;
  REP(i,n) s.push_back(i);
  vector<ll> graph_dist = dijkstra(n*(1<<k), s, graph_adj);

  ll ans = 1e18;
  REP(i,n) {
    ans = min(ans, graph_dist[i + ((1<<k)-1)*n]);
  }

  printf("%lld\n", ans);
}