DailyProgrammer #197 Intermediate Dijikstra

main.cpp

#include <iostream>
#include <string>
#include <vector>
#include <fstream>
#include <tuple>
#include <algorithm>
#include <climits>
#include <map>
#include <set>

struct Road
{
    char p1, p2;
    std::string name;
    int t1, t2, t3, t4;

    int get_length(int time) const {
        if (time >= 600 && time < 1000) return t1;
        else if (time >= 1000 && time < 1500) return t2;
        else if (time >= 1500 && time < 1900) return t3;
        else /*if (time >= 1900 || time < 600)*/ return t4;
    }
};

std::map<char, int> nodes;
std::map<char, char> prevs;

std::vector<Road> load_roads(){
    std::vector<Road> roads;

    std::ifstream f("input.txt");

    std::string temp;
    Road road;
    while (true) {
        f >> road.p1 >> road.p2 >> road.name;
        while (road.name.find('"', 1) == std::string::npos) {
            f >> temp;
            road.name += " " + temp;
        }
        road.name = road.name.substr(1, road.name.size() - 2);
        f >> road.t1 >> road.t2 >> road.t3 >> road.t4;

        if (!f)
            break;

        nodes[road.p1] = INT_MAX;
        nodes[road.p2] = INT_MAX;

        roads.push_back(road);
    }
    return roads;
}

std::tuple<std::vector<char>, int> solve(char start, char goal, int time, const std::vector<Road> &all_roads)
{
    std::set<char> unvisited;
    for(auto& kv : nodes){
        kv.second = INT_MAX;
        unvisited.insert(kv.first);
    }
    nodes[start] = 0;

    char position = start;
    while (position != goal){
        unvisited.erase(position);

        int length = nodes[position];

        std::vector<Road> best, solve;
        int bestLength = INT_MAX, solveLength;
        for (auto& next_road : all_roads) {
            char next;
            if (next_road.p1 == position)
                next = next_road.p2;
            else if (next_road.p2 == position)
                next = next_road.p1;
            else
                continue;
            if(unvisited.find(next) == unvisited.end())
                continue;

            int len = next_road.get_length(time);

            if(nodes[next] > length + len)
                nodes[next] = length + len;
        }

        auto smallest = *std::min_element(unvisited.begin(), unvisited.end(), [](char c1, char c2){return nodes[c1] < nodes[c2];});
        prevs[smallest] = position;

        position = smallest;
    }

    std::vector<char> path;

    char prev = goal;
    while(prev != start){
        path.insert(path.begin(), prev);
        prev = prevs[prev];
    }

    return std::make_tuple(path, nodes[goal]);
}

int main(){
    auto roads = load_roads();

    std::ifstream f("queries.txt");

    char start, end; int time;
    while (f >> start >> end >> time) {
        std::cout << start << " " << end << " " << time << "\n";

        std::vector<char> solution; int length;
        std::cout<<"b"<<std::endl;
        std::tie(solution, length) = solve(start, end, time, roads);

        if (solution.empty())
            continue;

        std::cout << length << " ";
        for (auto &road : solution)
            std::cout << road << ", ";
        std::cout << "\n\n";
    }
}