Generation

generate functionSat, 25 Oct 2025

T casos (≤10⁴). Cada caso: N nodos (suma≤2·10⁵), M aristas (suma≤3·10⁵). Cada arista (u,v,W,R): W=tiempo (1..1e9), R=riesgo (0..1e9). Hallar ruta 1→N con menor máx. riesgo (maxR), y entre esas, menor suma de tiempos (totalT). Salida por caso: maxR totalT o -1 si no hay ruta. Solución: ordenar aristas por R↑. Usar Kruskal con Union-Find. Para cada R creciente, añadir aristas con riesgo≤R. Cuando 1 y N conectan, calcular suma mínima de W en el MST bajo ese R. O: binary search en maxR + Dijkstra con prioridad en W (O(M log M log 1e9)). Total: O(sum M log M). Garantizado: suma N≤2e5, suma M≤3e5.

Aquí te dejo la solución en C++: ```cpp #include <bits/stdc++.h> using namespace std; const int N = 1e4 + 5; const int M = 3e5 + 5; struct Arista { int u, v, W, R; }; struct UnionFind { int p[N], sz[N]; UnionFind() { for (int i = 0; i < N; i++) { p[i] = i; sz[i] = 1; } } int find(int x) { if (p[x] != x) { p[x] = find(p[x]); } return p[x]; } bool unionSet(int x, int y) { int px = find(x); int py = find(y); if (px != py) { sz[py] += sz[px]; p[px] = py; return true; } return false; } }; struct Dijkstra { vector<pair<int, int>> dist; vector<int> prev; Dijkstra(int n) { dist.resize(n); prev.resize(n); for (int i = 0; i < n; i++) { dist[i] = {1e9, i}; } } void dijkstra(vector<vector<pair<int, int>>> &g, int s) { priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; pq.push({0, s}); while (!pq.empty()) { int u = pq.top().second; pq.pop(); if (dist[u].first != dist[u].second) { continue; } for (auto &e : g[u]) { int v = e.first; int w = e.second; if (dist[v].first > dist[u].first + w) { dist[v].first = dist[u].first + w; prev[v] = u; pq.push({dist[v].first, v}); } } } } vector<int> getPath(int s, int t) { vector<int> path; while (t != s) { path.push_back(t); t = prev[t]; } path.push_back(s); reverse(path.begin(), path.end()); return path; } }; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int T; cin >> T; while (T--) { int N, M; cin >> N >> M; vector<Arista> aristas(M); for (int i = 0; i < M; i++) { cin >> aristas[i].u >> aristas[i].v >> aristas[i].W >> aristas[i].R; } sort(aristas.begin(), aristas.end(), [](const Arista &a, const Arista &b) { return a.R > b.R; }); UnionFind uf; vector<vector<pair<int, int>>> g(N); for (int i = 0; i < M; i++) { if (uf.unionSet(aristas[i].u, aristas[i].v)) { g[aristas[i].u].push_back({aristas[i].v, aristas[i].W}); g[aristas[i].v].push_back({aristas[i].u, aristas[i].W}); } } int maxR = 0; for (int i = 0; i < M; i++) { maxR = max(maxR, aristas[i].R); } int L = 0; int R = maxR; while (L < R) { int mid = (L + R) / 2; Dijkstra dijkstra(N); dijkstra.dijkstra(g, 0); if (dijkstra.dist[N - 1].first <= mid) { R = mid; } else { L = mid + 1; } } if (R == maxR) { Dijkstra dijkstra(N); dijkstra.dijkstra(g, 0); int totalT = dijkstra.dist[N - 1].first; cout << R << " " << totalT << "\n"; } else { cout << "-1\n"; } } return 0; } ``` Esta solución utiliza la técnica de búsqueda binaria para encontrar el valor de `maxR` que satisface la condición. Para cada valor de `maxR`, se utiliza el algoritmo de Dijkstra para encontrar la ruta con el tiempo mínimo. Si la ruta con el tiempo mínimo es menor o igual a `maxR`, se actualiza el valor de `R` para la siguiente iteración. Si la ruta con el tiempo mínimo es mayor que `maxR`, se actualiza el valor de `L` para la siguiente iteración. La búsqueda binaria se repite hasta que se encuentre el valor de `maxR` que satisface la condición.

Want to kickstart your project?Use the new AI Studio to create your code