Mój kolega napisał ten program, tylko nie daje gwarancji, że w 100% dobrze działa.
Ale lepsze to, niż nic...
BTW. podaj nazwę uczelni, wydział i numer albumu.
Pomożemy Ci skończyć te studia ASAP.
#include <iostream>
#include <fstream>
#include <string>
#include <unordered_map>
#include <vector>
#include <queue>
#include <limits>
using namespace std;
struct Edge {
string destination;
int distance;
Edge(string dest, int dist) : destination(dest), distance(dist) {}
};
// Graph class representing the map of cities and roads
class Graph {
unordered_map<string, vector<Edge>> adjacency_list;
public:
// Add an edge to the graph
void addEdge(string source, string destination, int distance) {
adjacency_list[source].emplace_back(destination, distance);
}
// Find the shortest path using Dijkstra's algorithm
vector<pair<string, int>> shortestPath(string start, string end) {
unordered_map<string, int> distance;
unordered_map<string, string> previous;
priority_queue<pair<int, string>, vector<pair<int, string>>, greater<pair<int, string>>> pq;
for (const auto& pair : adjacency_list) {
string vertex = pair.first;
distance[vertex] = numeric_limits<int>::max();
previous[vertex] = "";
}
distance[start] = 0;
pq.push({0, start});
while (!pq.empty()) {
string u = pq.top().second;
pq.pop();
for (const auto& edge : adjacency_list[u]) {
string v = edge.destination;
int alt = distance[u] + edge.distance;
if (alt < distance[v]) {
distance[v] = alt;
previous[v] = u;
pq.push({alt, v});
}
}
}
vector<pair<string, int>> path;
string current = end;
while (!previous[current].empty()) {
path.emplace_back(current, distance[current]);
current = previous[current];
}
path.emplace_back(start, distance[start]);
reverse(path.begin(), path.end());
return path;
}
};
// Function to read roads from input file and construct graph
void readRoads(const string& filename, Graph& graph) {
ifstream file(filename);
if (file.is_open()) {
string source, destination;
int distance;
while (file >> source >> destination >> distance) {
graph.addEdge(source, destination, distance);
}
file.close();
} else {
cerr << "Unable to open file: " << filename << endl;
}
}
// Function to process and find shortest paths for given routes
void processRoutes(const string& filename, Graph& graph, ofstream& outfile) {
ifstream file(filename);
if (file.is_open()) {
string source, destination;
while (file >> source >> destination) {
auto path = graph.shortestPath(source, destination);
outfile << "trasa: " << source << " --> " << destination << " (" << path.back().second << " km):" << endl;
for (size_t i = 0; i < path.size() - 1; ++i) {
outfile << path[i].first << " --> " << path[i + 1].first << " " << path[i + 1].second << " km" << endl;
}
outfile << endl;
}
file.close();
} else {
cerr << "Unable to open file: " << filename << endl;
}
}
int main(int argc, char* argv[]) {
if (argc != 7) {
cerr << "Usage: " << argv[0] << " -d <roads_input_file> -t <routes_input_file> -o <output_file>" << endl;
return 1;
}
string roadsInputFile, routesInputFile, outputFile;
// Parsing command line arguments
for (int i = 1; i < argc; ++i) {
if (string(argv[i]) == "-d") {
roadsInputFile = argv[++i];
} else if (string(argv[i]) == "-t") {
routesInputFile = argv[++i];
} else if (string(argv[i]) == "-o") {
outputFile = argv[++i];
}
}
Graph graph;
readRoads(roadsInputFile, graph);
ofstream outfile(outputFile);
if (outfile.is_open()) {
processRoutes(routesInputFile, graph, outfile);
outfile.close();
} else {
cerr << "Unable to open output file: " << outputFile << endl;
return 1;
}
return 0;
}