#include <iostream> #include <vector> #include <queue> #include <algorithm> #include <utility> #include <memory> using namespace std; using Grafo = vector<vector<pair<int,int>>>; // arista = < coste, destino > const int INF = 1e9; class Dijkstra { public: Dijkstra() {} Dijkstra(Grafo const& g, size_t origen) : distTo(g.size(), INF) { distTo[origen] = 0; pq.push({0,origen}); while (!pq.empty()) { auto a = pq.top(); pq.pop(); if (a.first > distTo[a.second]) { continue; } for (auto ar : g[a.second]) { relax(g, a.second, ar); } } } ~Dijkstra(){} int valor(size_t w) { return distTo[w]; } bool hayCamino(size_t w) { return distTo[w] != INF; } private: std::vector<int> distTo; priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; void relax(Grafo const& g, int v, pair<int,int> const& e){ size_t w = e.second; if (distTo[w] > distTo[v] + e.first) { distTo[w] = distTo[v] + e.first; pq.push({distTo[w], w}); } } }; bool resuelveCaso() { int V, E; cin >> V >> E; if (!cin) return false; // leemos grafo Grafo grafo(V); int u, v, c; while (E--) { cin >> u >> v >> c; grafo[u-1].push_back({c,v-1}); grafo[v-1].push_back({c,u-1}); } int cursos; cin >> cursos; // compartimos informaci�n entre diferentes cursos vector<shared_ptr<Dijkstra>> distancias(V); for (int curso = 0; curso < cursos; ++curso) { int ncoles; cin >> ncoles; vector<bool> es_cole(V, false); vector<int> los_coles; for (int i = 0; i < ncoles; ++i) { cin >> c; es_cole[c-1] = true; los_coles.push_back(c-1); } // calculamos la mejor forma de ir desde cualquiera de los coles a todos los dem�s v�rtices for (int i = 0; i < ncoles; ++i) { if (distancias[los_coles[i]] == nullptr) { distancias[los_coles[i]] = make_shared<Dijkstra>(grafo,los_coles[i]); } } // ahora probamos todas las permutaciones de los coles vector<int> perm(ncoles); for (int i = 0; i < ncoles; ++i) { perm[i] = i; } int respuesta = INF; int mejor_casa{}; do { // calculamos el coste de unir los coles int unir_coles = 0; for (int i = 0; i < ncoles-1; ++i) { unir_coles += distancias[los_coles[perm[i]]]->valor(los_coles[perm[i+1]]); } // probamos con todos los posibles v�rtices origen for (int v = 0; v < V; ++v) { if (!es_cole[v]) { int completo = distancias[los_coles[perm[0]]]->valor(v) + unir_coles + distancias[los_coles[perm[ncoles-1]]]->valor(v); if (completo < respuesta || (completo == respuesta && v < mejor_casa)) { respuesta = completo; mejor_casa = v; } } } } while (next_permutation(perm.begin(), perm.end())); cout << mejor_casa+1 << ' ' << respuesta << '\n'; } if (cursos > 0) cout << "---\n"; return true; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); while (resuelveCaso()); return 0; } /* 2 1 1 2 1 1 1 1 4 5 1 2 1 1 3 1 1 4 1 2 3 1 2 4 1 2 2 1 2 3 4 1 2 */