×

INSQ15_F - Editorial

Author: vishfrnds
Tester: codefor6768
Editorialist: vishfrnds

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
* 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".

47118
accept rate: 0%

 1 Nice Editorial :) answered 07 Sep '15, 09:31 31●3 accept rate: 0%
 0 Nice Problem :) And Nice Editorial too :) answered 13 Sep '15, 19:11 79●1●9 accept rate: 0%
 0 The author's solution is giving wrong answer. answered 10 Oct, 00:57 1 accept rate: 0%
 0 Can anyone check why my solution is wrong. I have done as told in the editorial. My Solution : https://www.codechef.com/viewsolution/16228356 answered 11 Nov, 22:55 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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,951 times

last updated: 11 Nov, 22:55