PROBLEM LINK:
Author: vishfrnds
Tester: codefor6768
Editorialist: vishfrnds
DIFFICULTY:
MEDIUM
PREREQUISITES:
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;
}
