You are not logged in. Please login at www.codechef.com to post your questions!

×

INSQ15_F - Editorial

1
1

PROBLEM LINK:

Practice
Contest

Author: vishfrnds
Tester: codefor6768
Editorialist: vishfrnds

DIFFICULTY:

MEDIUM

PREREQUISITES:

dijkstra's algorithm
basic graph theory

PROBLEM:

Given a graph of N nodes. i-th node has a height H[i], and cost C[i]. You can travel nodes in one of the mode either non-decreasing order of height or non-increasing order of height of nodes. Whenever you change mode on i-th node it will cost you C[i]. Find the path of minimum cost from node 1 to N.

QUICK EXPLANATION:

Split the given graph into two graphs each of N nodes. Where each graph have a subset directed edges of 0 cost, representing single mode only. Connect the corresponding nodes from both graph with undirected edge of cost C[i]. Add a source node and connect it with node 1 of both graphs with cost C[i]. Add a destination node and connect it with node N of both graphs with cost 0. Apply Dijkstra algorithm to find smallest cost path between source and destination.

EXPLANATION:

Make a copy of given graph G1, let it be G2. G1 will have a directed edge from node A to B if and only if H[A] <= H[B] and there was edge between A and B in orignal graph, delete all other edges. G2 will have a directed edge from node A to B if and only if H[A] >= H[B] and there was edge between A and B in orignal graph, delete all other edges.

Now G1 represents mode "up the road" (i.e. non-decreasing mode). Now G2 represents mode "down the road" (i.e. non-increasing mode).

All the edges in G1 and G2 have cost 0. This represent it will not cost you anything as long as you are in single graph.

Now to allow changing of mode we will connect corresponding nodes of both the graph with cost C[i] of that node. Thus, whenever you will change mode on i-th node it will cost C[i].

Now we will add a source and destination node. Source node will be connected to node 1 of G1 with cost C[1] and node 1 of G2 with cost C[1]. Because you need to pay to chose initial mode. Destination node will be connected to node N of G1 with cost 0 and node N of G2 with cost 0. Because it makes no difference wether you end up on G1's node N or G2's node N. So if given graph had n nodes e edges, final graph will have node N = 2 * n + 2 and edges E = e + n + 4

Now we will use dijkstra's algorithm to find minimum cost path from source to destination in this new graph.

AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution.

 /* -.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.
 * Created By : Vishwas Tripathi 
 * CSE, MNNIT-ALLAHABAD 
 * vishfrnds@gmail.com
 _._._._._._._._._._._._._._._._._._._._._.*/


#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

#define MP make_pair
#define pb push_back
#define X first
#define Y second

typedef long long ll;

#define INF (ll)1e18

long long dijk (int st, int end, vector<pair<int, int> > G[], int n) {
    vector<long long> dist (n, INF);
    dist[st] = 0;
    set<pair<long long, int> > q; // cost, node
    q.insert (make_pair (0, st));
    while (!q.empty ()) {
        pair<long long, int> top = *q.begin ();
        q.erase (q.begin ());
        int v = top.second;
        long long d = top.first;
        if (v == end)
            break;
        for (vector<pair<int, int> >::iterator it = G[v].begin (); it != G[v].end (); it++) {
            int v2 = it->first;
            long long cost = it->second;
            if (dist[v2] > dist[v] + cost) {
                if (dist[v2] != INF) {
                    q.erase (q.find (make_pair (dist[v2], v2)));
                }
                dist[v2] = dist[v] + cost;
                q.insert (make_pair (dist[v2], v2));
            }
        }
    }
    if (dist[end] == INF) {
        return -1;
    }
    return dist[end];
}

int main()
{
    int t, n, m, i, j, x, y;
    cin >> n >> m;
    vector<int> h(n + 1), c(n + 1);
    vector<pair<int, int> > G[2 * n + 2];
    for (i = 1; i <= n; i++) {
        cin >> h[i];
    }
    //G1 from 1 to N
    //G2 from N + 1 to 2 * N
    for (i = 1; i <= n; i++) {
        cin >> c[i];
        G[i].pb (MP (n + i, c[i]));
        G[n + i].pb (MP (i, c[i]));
    }
    for (i = 1; i < m; i++) {
        cin >> x >> y;
        if (h[x] <= h[y])
            G[x].pb (MP (y, 0));
        if (h[x] >= h[y])
            G[n + x].pb (MP (n + y, 0));
        if (h[y] <= h[x])
            G[y].pb (MP (x, 0));
        if (h[y] >= h[x])
            G[n + y].pb (MP (n + x, 0));
    }
    G[0].pb(MP (1, c[1]));
    G[0].pb(MP (n + 1, c[1]));
    G[n].pb(MP (2 * n + 1, 0));
    G[2 * n].pb(MP (2 * n + 1, 0));
    cout << dijk(0, 2 * n + 1, G, 2 * n + 2);
    return 0;
}
This question is marked "community wiki".

asked 07 Sep '15, 01:58

vishfrnds's gravatar image

6★vishfrnds
47118
accept rate: 0%

edited 09 Sep '15, 21:49


Nice Editorial :)

link

answered 07 Sep '15, 09:31

nishant_141077's gravatar image

5★nishant_141077
313
accept rate: 0%

Nice Problem :) And Nice Editorial too :)

link

answered 13 Sep '15, 19:11

vikky_codder's gravatar image

6★vikky_codder
7919
accept rate: 0%

The author's solution is giving wrong answer.

link

answered 10 Oct, 00:57

coder_anmol's gravatar image

4★coder_anmol
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×138
×38
×5
×3

question asked: 07 Sep '15, 01:58

question was seen: 1,803 times

last updated: 10 Oct, 00:57