map struct

.
Last edited on
Perhaps try recursive approach?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <fstream>
#include <map>

using namespace std;

void Show(const map<string, vector<pair<string,int>>>& flights)
{
    for(auto& src_map : flights)
    {
        cout << src_map.first << ":" << endl;
        for(auto& dest_price : src_map.second)
            cout << "  =>"<<dest_price.first << " " << dest_price.second << endl;
    }
}

void Fly(map<string, bool> visited, 
         const map<string, vector<pair<string,int>>>& flights,
         pair<string,int> dest_pair,
         const string& final_dest,
         string path,
         vector<pair<int,string>>& all_paths,
         int cost,
         int& best_cost,
         string& best_path
         )
{
    visited[dest_pair.first] = true;
    path += "=>"+dest_pair.first;
    cost += dest_pair.second;
    if (dest_pair.first==final_dest)
    {
        //cout << path << endl;
        all_paths.emplace_back(cost, path);
        if (cost < best_cost)
        {
            best_cost = cost;
            best_path = path;
        }
        return;
    }
    
    for (const auto& dest_pair : flights.at(dest_pair.first))
    {
        if (!visited[dest_pair.first])
        {
            Fly(visited,
                flights,
                dest_pair,
                final_dest,
                path,
                all_paths,
                cost,
                best_cost,
                best_path);
        }
    }
}

void FindBestFlights(const map<string, bool>& sources,
                     const map<string, vector<pair<string,int>>>& flights,
                     const string& start, 
                     const string& final_dest)
{
    if (sources.count(start)==0 || sources.count(final_dest)==0)
    {
        cout << "One or more of ["<<start<<", "<<final_dest<<"] do not exist.\n";
        return;
    }
    string path = start;
    vector<pair<int, string>> all_paths;  // Total cost with total path
    int cost = 0;
    int best_cost = 999999;
    string best_path;
    
    for (const auto& dest_pair : flights.at(start))
    {
        Fly(sources, flights, dest_pair, final_dest,
            path, all_paths, cost, best_cost, best_path);
    }
    
    cout << "best_cost: $" << best_cost << endl;
    cout << "best_path: " << best_path << endl << endl;
    
    cout << "all_paths:"<<endl;
    for (auto& cp : all_paths)
        cout << "  $" << setw(5) << cp.first << "  " << cp.second << endl;
    
}

int main() 
{
    string file_name("flights.txt");
    ifstream ifs(file_name);
    if (!ifs)
    {
        cout << "Unable to open \""<<file_name<<"\".  Please check it exists and not in use.\n";
        return -1;
    }
    
    map<string, vector<pair<string,int>>> flights;
    map<string, bool> sources;
    string src, dst;
    int price;
    while (ifs >> src >> price >> dst )
    {
        flights[src].emplace_back(dst,price);
        sources[src] = false;
    }
    //Show(flights);
    
    src = "LGA";
    dst = "HND";
    sources[src] = true;  // Mark as visited
    FindBestFlights(sources, flights, src, dst);
    
    return 0;
}


can test at https://repl.it/repls/ElectricEmbellishedApi (flights.txt is there too)

best_cost: $582
best_path: LGA=>ORD=>YVR=>ANC=>ICN=>HND

all_paths:
  $ 1159  LGA=>SFO=>ORD=>YVR=>HND
  $ 1003  LGA=>SFO=>ORD=>YVR=>ANC=>ICN=>HND
  $ 1023  LGA=>SFO=>ORD=>YVR=>ICN=>HND
  $  802  LGA=>SFO=>HND
  $  852  LGA=>LAX=>HND
  $  738  LGA=>ORD=>YVR=>HND
  $  582  LGA=>ORD=>YVR=>ANC=>ICN=>HND
  $  602  LGA=>ORD=>YVR=>ICN=>HND
  $  739  LGA=>ORD=>SFO=>HND
  $ 1118  LGA=>YVR=>ORD=>SFO=>HND
  $  759  LGA=>YVR=>HND
  $  603  LGA=>YVR=>ANC=>ICN=>HND
  $  623  LGA=>YVR=>ICN=>HND
  $ 1365  LGA=>YOW=>YVR=>ORD=>SFO=>HND
  $ 1006  LGA=>YOW=>YVR=>HND
  $  850  LGA=>YOW=>YVR=>ANC=>ICN=>HND
  $  870  LGA=>YOW=>YVR=>ICN=>HND


Edit: for some reason to allow const iteration through flights map, it doesn't like operator[] on that map -- i needed to instead use .at() .
Edit2: realized it's because operator[] performs insertion if that key doesn't exist.
Edit3: moved the setting of initial visited state to main() so that all params of FindBestFlights() could be const
Last edited on
Registered users can post here. Sign in or register to post.