temp.cpp

struct State
{
    int vertex, cost;
    
    State(int v, int c)
    {
        vertex = v;
        cost = c;
    }
};

class Solution2
{
public:
    vector<int> shortestPath(vector<vector<int>>& graph, int source, int target)
    {
        int n = graph.size();
        vector<int> parents(n, -1);
        auto comp = [](const State& lhs, const State& rhs)
        {
            return lhs.cost > rhs.cost;
        };
        priority_queue<State, vector<State>, decltype(comp)> pq(comp);
        pq.emplace(source, 0);
        vector<bool> visited(n, false);
        visited[source] = true;
        bool found = false;
        while(!found)
        {
            auto curr = pq.top();
            pq.pop();
            int v = curr.vertex, cost = curr.cost;
            for(auto& u : graph[v])
            {
                if(!visited[u])
                {
                    parents[u] = v;
                    if(u == target)
                    {
                        found = true;
                        break;
                    }
                    int fee = abs(v - u);
                    fee *= fee;
                    pq.emplace(u, fee + cost);
                    visited[u] = true;
                }
            }
        }
        
        vector<int> path;
        int curr = target;
        while(curr != -1)
        {
            path.push_back(curr);
            curr = parents[curr];
        }
        reverse(path.begin(), path.end());
        return path;
    }
};

int main()
{
    vector<string> words = {"hello","word"};
    vector<pair<string, string>> equations = {{"a", "b"}, {"b", "c"}};
    vector<double> values = {2.0, 3.0};
    vector<pair<string, string>> queries = {{"a", "c"}, {"b", "c"}, {"a", "e"}, {"a", "a"}, {"x", "x"}};
    vector<Point> g = {{1,1},{2,2},{2,0},{2,4},{3,3},{4,2}};
    vector<vector<int>> matrix = {{1,2},{3},{3,4},{4},{}};
    vector<int> v1 = {6,5,8,9,7,1,10,2,3,4}, v2 = {0,0,1,1}, worker = {92,10,85,84,82};
    vector<vector<double>> v3 = {{1.0, 1.0}};
    Solution2 sol;
    auto res = sol.shortestPath(matrix, 0, 4);
    
}