INSQ15_F - Editorial

dijkstra
fcar
insq15_f
insq2015

#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*, and cost C*.
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*.
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*.
Add a source node and connect it with node 1 of both graphs with cost C*.
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** 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** 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* of that node.
Thus, whenever you will change mode on i-th node it will cost C*.

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*;
	}
	//G1 from 1 to N
	//G2 from N + 1 to 2 * N
	for (i = 1; i <= n; i++) {
		cin >> c*;
		G*.pb (MP (n + i, c*));
		G[n + i].pb (MP (i, c*));
	}
	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;
}

#2

Nice Editorial :slight_smile:


#3

Nice Problem :slight_smile: And Nice Editorial too :slight_smile:


#4

The author’s solution is giving wrong answer.


#5

Can anyone check why my solution is wrong. I have done as told in the editorial.

My Solution : https://www.codechef.com/viewsolution/16228356


#6

Very nice editorial!


#7

This was a great technique of dividing the graph into parts and again joining it. Really great problem would recommend others to do this.