Untitled

mail@pastecode.io avatar
unknown
c_cpp
2 months ago
2.3 kB
8
Indexable
Never

int RequiredFunction(map<string, int> v , map<pair<string , string> , int> edges, string start , string end){
    // adjiacency list for the directed graph
    map<string , vector<pair<string , int>>> adj;
    for(auto i : edges){ 
        adj[i.first.first].push_back({i.first.second , i.second});
    }
    map<string , int> dp; // dp to store the minimum cost to reach the end from the current vertix
    function<int(string)> dfs = [&] (string curr){
        if(curr == end) return 0;

        if(dp.find(curr) != dp.end()) return dp[curr]; // if we already visited this vertix return the value
        int &ans = dp[curr];
        ans = 1e9; // set the value to infinity
        for(auto i : adj[curr]){ 
            ans = min(ans , dfs(i.first) + i.second); // dp[u] = min(dp[u] , dp[v] + weight of the edge between u and v) for all v in adj[u]
        }
        return ans;
    };
    return dfs(start);
};

void swap(pair<string, string> &a , map<string , int> &v){
    if(v[a.first] > v[a.second]) return;
    swap(a.first , a.second);
}


void nane(){
    map<string, int> vertices1;
    // vertix hight
    vertices1["S"] = 12;
    vertices1["A1"] = 8;
    vertices1["A2"] = 2;
    vertices1["A3"] = 9;
    vertices1["T"] = 4;
    // edges    
    pair<string, string> connection11 = {"S", "A1"};
    pair<string, string> connection12 = {"A1", "A2"};
    pair<string, string> connection13 ={"A2", "T"};
    pair<string, string> connection14 = {"S", "T"};
    pair<string, string>connection15 = {"A3", "S"};
    pair<string, string> connection16 = {"A3", "T"};
    // sort the edges so the first vertix is the highest because we can't go from lower vertix to higher vertix
    swap(connection11 , vertices1);
    swap(connection12 , vertices1);
    swap(connection13 , vertices1);
    swap(connection14 , vertices1);
    swap(connection15 , vertices1);
    swap(connection16 , vertices1);
    // edges weight
    map<pair<string, string>, int> edges1;
    edges1[connection11] = 1;
    edges1[connection12] = 1;
    edges1[connection13] = 1;
    edges1[connection14] = 12;
    edges1[connection15] = 5;
    edges1[connection16] = 6;
    for(auto &i : edges1){
        cout << i.first.first << " " << i.first.second << " " << i.second << endl;
    }
    cout << RequiredFunction(vertices1 , edges1 , "S" , "T") << endl;
        
    

}
Leave a Comment