Блог пользователя rahul_1234

Автор rahul_1234, история, 6 лет назад, По-английски

You are given a list of edges in a graph and for each pair of vertices that are connected by an edge, there are two edges between them, one curved edge and one straight edge i.e. the tuple (x, y, w1, w2) means that between vertices x and y, there is a straight edge with weight w1 and a curved edge with weight w2. You are given two vertices a and b and you have to go from a to b through a series of edges such that in the entire path you can use at most 1 curved edge.

Your task is to find the shortest path from a to b satisfying the above condition.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Build 2 copies of a directed graph with only straight edges, and add curved edges from vertex a of graph 1 to vertex b of graph 2, now run dijkstra on the new graph.

»
6 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

You didn't indicate if the graph is directed or undirected. Assuming the graph is undirected I have come up with this following solution:

Run dijkstra from node a. Let's call Da[i] be the shortest path to node i from node a using only straight edges.

Again run dijkstra from node b. Let's call Db[i] be the shortest path to node i from node b using only straight edges.

Let ans be our final answer. Initialize ans by Da[b] because this is the answer for using no curved edges.

So ans=Da[b];

Now for using exactly one curved edge we can check for every edge (u,v) by the following way,

ans=min(ans,Da[u]+weight of curved edge (u,v) +Db[v])

ans=min(ans,Da[v]+weight of curved edge (v,u) +Db[u])

Finally ans will be the answer for using at most one curved edge.

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Found this problem on GFG: Problem Link!

class Solution {
  public:
    int shortestPath(int n, int m, int a, int b, vector<vector<int>> &edges) {
        vector<pair<int, pair<int, int>>> graph[n];
        a -= 1;
        b -= 1;
        for(auto &a : edges){
            a[0] -= 1;
            a[1] -= 1;
            graph[a[0]].push_back({a[1], {a[2], a[3]}});
            graph[a[1]].push_back({a[0], {a[2], a[3]}});
        }
        priority_queue<pair<int, int>, vector<pair<int, int>>,
                            greater<pair<int, int>>> pq;
        int dist[n][2];
        for(int i = 0; i < n; i++)
            dist[i][0] = 1e9, dist[i][1] = 1e9;
        dist[a][0] = 0;
        dist[a][1] = 0;
        pq.push({0, a});
        while( !pq.empty() ){
            auto front = pq.top();
            pq.pop();
            int par = front.second;
            int newDist = front.first;
            for(auto &child : graph[par]){
                int cNode = child.first;
                int curve = child.second.second;
                int st = child.second.first;
                if( dist[cNode][0] > dist[par][1] + curve ){
                    dist[cNode][0] = dist[par][1] + curve;
                    pq.push({dist[cNode][0], cNode});
                }
                if( dist[cNode][0] > dist[par][0] + st ){
                    dist[cNode][0] = dist[par][0] + st;
                    pq.push({dist[cNode][0], cNode});
                }
                if( dist[cNode][1] > dist[par][1] + st ){
                    dist[cNode][1] = dist[par][1] + st;
                    pq.push({dist[cNode][1], cNode});
                }
            }
        }
        int resDist = min(dist[b][0], dist[b][1]);
        if( resDist == 1e9 ) return -1;
        return resDist;
    }
};