Solução de João Guilherme
Para ver o problema original, clique aqui.
Esse problema é uma simples modificação do algoritmo de Floyd-Warshall (uma solução usando Djikstra também é possível, e ambas estão contidas no código). Primeiro notamos que a complexidade do algoritmo passa bem no tempo da questão, segundo vemos como o algoritmo funciona, ele pega o melhor caminho do vértice i ao j usando apenas vértices no conjunto {1, 2, ..., k} para cada k de 1 a n. No nosso caso nós definimos o melhor caminho como sendo o que tem a maior aresta mínima, assim em vez de tomar o mínimo entre o caminho que temos de i a j e o caminho de i a k + o caminho de k a j, tomamos o máximo entre o caminho de i a j e o peso mínimo entre as arestas no caminho de i a k e de k a j. Por fim imprimimos a distância entre as duas cidades desejadas.
Segue código para melhor entendimento.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <bits/stdc++.h> | |
| #define ff first | |
| #define ss second | |
| using namespace std; | |
| typedef pair<int, int> pii; | |
| vector <pii> adj[256]; | |
| map <string, int> mapa; | |
| int G[256][256], cont, dist[256]; | |
| void fw(int n){ | |
| for(int k = 0; k < n; ++k) | |
| for(int i = 0; i < n; ++i) | |
| for(int j = 0; j < n; ++j) | |
| G[i][j] = max(G[i][j], min(G[i][k], G[k][j])); | |
| return; | |
| } | |
| void dijkstra(int n, int k){ | |
| int idx, v, d; | |
| dist[k] = (1 << 29); | |
| priority_queue < pii > pq; | |
| pq.push(pii((1 << 29), k)); | |
| while(pq.size()){ | |
| idx = -1; | |
| while(pq.size()){ | |
| v = pq.top().ss; | |
| d = pq.top().ff; | |
| pq.pop(); | |
| if(dist[v] != d) continue; | |
| idx = v; | |
| break; | |
| } | |
| if(idx == -1) break; | |
| for(pii const & e : adj[idx]) | |
| if(dist[e.second] < min(dist[idx], e.first)){ | |
| dist[e.second] = min(dist[idx], e.first); | |
| pq.push(pii(dist[e.second], e.second)); | |
| } | |
| } | |
| return; | |
| } | |
| void initialize(int n){ | |
| cont = 0; | |
| mapa.clear(); | |
| memset(G, 0, sizeof G); | |
| for(int i = 1; i <= 255; ++i) adj[i].clear(); | |
| for(int i = 1; i <= 255; ++i) dist[i] = 0; | |
| return; | |
| } | |
| int main(){ | |
| ios_base::sync_with_stdio(0); | |
| int n, r, aux; | |
| string aus, aur; | |
| cin >> n >> r; | |
| for(int t = 1; (n || r); ++t){ | |
| initialize(n); | |
| for(int i = 0; i < r; ++i){ | |
| cin >> aus >> aur >> aux; | |
| if(!mapa.count(aus)) | |
| mapa[aus] = ++cont; | |
| if(!mapa.count(aur)) | |
| mapa[aur] = ++cont; | |
| G[mapa[aus]][mapa[aur]] = G[mapa[aur]][mapa[aus]] = aux; | |
| //adj[mapa[aus]].push_back(pii(aux, mapa[aur])); | |
| //adj[mapa[aur]].push_back(pii(aux, mapa[aus])); | |
| } | |
| fw(n); | |
| cin >> aus >> aur; | |
| //dijkstra(n, mapa[aus]); | |
| //cout << "Scenario #" << t << "\n" << dist[mapa[aur]] << " tons\n\n"; | |
| cout << "Scenario #" << t << "\n" << G[mapa[aur]][mapa[aus]] << " tons\n\n"; | |
| cin >> n >> r; | |
| } | |
| return 0; | |
| } |