2 problema 2: trenuri 2.1 Enunt, Profund impresionat de trenurile din Elvet,ia (s,i…
- User
2 problema 2: trenuri 2.1 Enunt, Profund impresionat de trenurile din Elvet,ia (s,i pentru c˘a s,i-a plictisit tot,i prietenii vorbind despre ele), Bogdan Urzescu a decis s˘a mearg˘a într-o c˘al˘atorie lung˘a. Ca orice programator care se respect˘a, Bogdan a desc˘arcat o list˘a de M curse directe cu trenul între diverse oras,e. Pentru c˘a el este preocupat de criptomonede, v˘a cere ajutorul cu urm˘atoarea problem˘a: s,tiind oras,ul din care pleac˘a s,i oras,ul în care acesta îs,i dores,te s˘a ajung˘a, spunet,i-i num˘arul maxim de oras,e distincte pe care le poate vizita. Se garanteaz˘a c˘a Bogdan poate ajunge la destinat,ie. Este important de ment,ionat c˘a nu exist˘a niciun ciclu în ret,eaua de trenuri, adic˘a, pornind din orice oras, , nu se poate ajunge din nou în acel oras, , indiferent de cursele alese. 2.2 Date de intrare Pe prima linie din fis,ierul trenuri.in se vor afla denumirile oras,ului din care Bogdan va pleca s,i oras,ul în care Bogdan vrea s˘a ajung˘a, separate printr-un spat,iu. Pe a doua linie se va afla un singur num˘ar natural M, reprezentând num˘arul de trasee directe. Pe urm˘atoarele M linii se vor afla câte dou˘a s,iruri de caractere x s,i y, reprezentând faptul c˘a exist˘a o curs˘a direct˘a de la oras,ul x la oras,ul y. 2.3 Date de ies,ire În fis,ierul trenuri.out vet,i afis,a un singur num˘ar, reprezentând num˘arul maxim de oras,e distincte care pot fi vizitate. 2.4 Restrict,ii s,i precizări • 1 ⩽ M ⩽ 2 ∗ 105 • Prin o curs˘a orientat˘a de la x la y se înt,elege c˘a putem ajunge din oras,ul x în oras,ul y folosind acea curs˘a, dar nu s,i invers. • Numele oras,elor sunt formate doar din litere mici ale alfabetului englez. • Numele oras,elor sunt reale. problema 2: trenuri 6 2.5 Testare s,i punctare • Punctajul maxim este de 40 puncte. • Timpul de execut,ie: – C/C++: 3 s – Java: 4 s • Sursa care cont,ine funct,ia main trebuie obligatoriu denumit˘a: trenuri.c, trenuri.cpp sau Trenuri.java. 2.6 Exemple trenuri.in trenuri.out Explicat,ie bucuresti timisoara 4 bucuresti sibiu sibiu timisoara sibiu cluj cluj timisoara 4 Exist˘a dou˘a posibilit˘at,i de a ajunge în Timis,oara: Bucures,ti → Sibiu → Timis,oara s,i Bucures,ti → Sibiu → Cluj → Timis,oara. Al doilea traseu trece prin 4 oras,e, fiind s,i num˘arul maxim de oras,e care pot fi vizitate.
make in cpp
- Assistant
To solve the problem, we need to find the longest path in a directed acyclic graph (DAG) between two given cities. The restriction that no cycles are in the network of trains allows us to treat the problem using techniques designed to work with DAGs, such as dynamic programming or depth-first search (DFS). The idea is to utilize a DFS to find the longest path between the starting city and the destination city.
Below is a possible solution in C++, which reads the train routes from an input file named "trenuri.in" and outputs the maximum number of distinct cities that can be visited to a file named "trenuri.out".
#include <iostream> #include <fstream> #include <vector> #include <unordered_map> #include <algorithm> #include <string> using namespace std; // Utilize a map to convert city names to unique indices for easier handling unordered_map<string, int> city_map; vector<vector<int>> adj; // adjacency list for graph vector<int> visited; // visited marking for cities in DFS vector<int> dp; // stores the longest path ending at each node int getCityIndex(const string& city) { if (city_map.find(city) == city_map.end()) { int new_index = city_map.size(); city_map[city] = new_index; adj.push_back(vector<int>()); } return city_map[city]; } // DFS to find the longest path in DAG int dfs(int u) { if (visited[u]) return dp[u]; visited[u] = 1; int max_length = 0; for (int v : adj[u]) { max_length = max(max_length, dfs(v)); } dp[u] = max_length + 1; return dp[u]; } int main() { ifstream fin("trenuri.in"); ofstream fout("trenuri.out"); string start_city, end_city; fin >> start_city >> end_city; int M; fin >> M; adj.clear(); city_map.clear(); for (int i = 0; i < M; ++i) { string x, y; fin >> x >> y; int from = getCityIndex(x); int to = getCityIndex(y); adj[from].push_back(to); } int start_index = getCityIndex(start_city); int end_index = getCityIndex(end_city); // Prepare lookup arrays visited.assign(city_map.size(), 0); dp.assign(city_map.size(), 0); // Calculate longest path from start_index fout << dfs(start_index) - 1 << endl; // -1 to exclude the start city itself from the count fin.close(); fout.close(); return 0; }This solution is based on the following steps:
- Mapping city names to unique indices.
- Constructing an adjacency list representation of the graph.
- Using a DFS-method augmented with dynamic programming (memoization) to determine the longest path from the starting city in the DAG.
- Reporting the length of the longest path minus one (to exclude the starting city from the count as we want only the visited cities counted).
This code should efficiently handle the constraints of up to 200,000 direct routes.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.