PROBLEM LINK:
Setter- Erfan Alimohammadi
Tester- Roman Bilyi
Editorialist- Abhishek Pandey
DIFFICULTY:
EASY
PRE-REQUISITES:
Floyd Warshall (All Pair Shortest Path). Some basic knowledge of Dynamic Programming helps.
PROBLEM:
Given a graph of N nodes and R edges, help professor reach from Node P to Node Q at minimum price if you are given the price of petrol at each node.
QUICK-EXPLANATION:
Key to AC- Floyd Warshall (x2) 
Apply Floyd Warshall on the graph to find shortest path between every pair of Nodes (i,j). Meaning, the least amount of petrol needed to reach a node j from Node i.
Once this is done, make a new directed (Why? Q1.) graph G' where there are edges between every pair of Node (u,v) with weight cost[v] * ShortestPath(v,u). Meaning, there is an edge from v to u with cost as that of reaching Node u (Starting from Node v) if we fill enough petrol at Node v.
Now all we need to do is to run a Floyd Warshall on this new Graph G` to find shortest path from P to Q.
EXPLANATION:
The quick explanation section pretty much sums it all. The main explanation section can hence, take the liberty to go into more basic stuff. The editorial is divided into following sections-
- Telling a little about Floyd Warshall (A very brief introduction to it - read link in pre requisite for detailed explanation)
- Making the new Graph G`.
As usual, answers to all the questions will be in Chef Vijju’s Corner 
(Each of the section will be in hidden boxes below, so that the experienced reader can skip appropriate parts.)
1. Floyd Warshall (Optional)
Floyd Warshall is used in graph theory problems where you need to find the shortest path between all pairs of Nodes for any kind of further processing. If you read the link at pre-requisite, and see the code given, it is pretty simple-
for (k = 0; k < V; k++) //Considering intermediate Node k
{
// Pick all vertices as source one by one
for (i = 0; i < V; i++)
{
// Pick all vertices as destination for the
// above picked source
for (j = 0; j < V; j++)
{
// If vertex k is on the shortest path from
// i to j, then update the value of dist[i][j]
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
The idea for this is, that, for every pair of nodes i and j, check if node k lies on the shortest path or not. It lies on shortest path if and only if the cost of Path from i to k and then from k to j is less than that of going from i to j originally. There are O(N^2) pairs of such nodes, i and j, and as any node can act as intermediate node between shortest path of some pair, the overall complexity goes up to O(N^3).
Most people are confused by the outermost loop of k, so just remember that it is performing the function related to intermediate node.
2. Making the New Graph G`
After applying Floyd Warshall once, we know the minimum amount of petrol to reach any node i from any node j. Now, we have to account for the fact that petrol cost can be different at each node, and hence decide the optimum route to reach node i.
Now, how to do it? 
Wait! See, the constraints for N are small! Hence, the simplest and the easiest way to achieve the above is to TRY THEM ALL!! 
.
In other words, to find the best city for filling petrol at (from which we directly code to city i) , we simply try filling petrol at every other city j and chose the one which gives the least cost!
Putting it formally, we make a new Directed Graph G` (try to figure out the reason behind directedness. Else, the answer is in bonus section.). In our new graph G`, we have edges between all pair of nodes, (u,v), with the weight as -
Weight of Edge from v to u = cost[v] * ShortestPath(v,u)
Expressing alternatively in friendlier terms-
Weight of Edge from u to v = cost[u] * ShortestPath(u,v)
This can be interpreted as - “Weight of Edge from Node u to Node v is the cost of petrol we need to fill at Node u to reach Node v without stopping for petrol at any node in between.”
Now, we have captured the Nodes, the edges and their weights appropriately. All that is left is to find what is the optimal path to reach city Q from city P. We are back to square one - we just need to repeat what we did earlier to find it.
Hence, doing a Floyd Warshall (again!) on this new Graph G` will fetch us the final answer!
SOLUTION
Setter
#include <iostream>
using namespace std;
const int maxn=402;
int n, m, source, destination;
long long int dist[maxn][maxn];
long long int price[maxn];
long long int dp[maxn];
void initialize();
void read();
void preprocess();
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
n = maxn;
initialize();
int t;
cin >> t;
while (t--) {
read();
preprocess();
dp[source]=0;
for(int counter=0; counter<n; counter++)
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
dp[i]=min(dp[i], dp[j]+dist[j][i]*price[j]);
cout<<dp[destination]<<endl;
initialize();
}
return 0;
}
void initialize(){
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
dist[i][j]=1000*1000*1000;
long long int inf=1000*1000*1000;
inf*=1000*1000*1000;
for(int i=0; i<n; i++)
dp[i]=inf;
}
void read(){
cin>>n>>m;
int v, u, w;
for(int i=0; i<m; i++){
cin>>v>>u>>w;
v--;
u--;
dist[u][v]=dist[v][u]=w;
}
for(int i=0; i<n; i++)
cin>>price[i];
cin>>source>>destination;
source--;
destination--;
}
void preprocess(){
for(int i=0; i<n; i++)
dist[i][i]=0;
for(int k=0; k<n; k++)
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
dist[i][j]=min(dist[i][j], dist[i][k]+dist[k][j]);
}
Tester
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define RFOR(i,b,a) for (int i = (b) - 1; i >= (a); i--)
#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a,value) memset(a, value, sizeof(a))
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
typedef long long Int;
typedef vector<int> VI;
typedef pair<int, int> PII;
const double PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000;
const Int LINF = INF * (Int) INF;
const int MAX = 307;
const int MOD = 998244353;
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
assert(cnt>0);
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
void assertEof(){
assert(getchar()==-1);
}
Int D[MAX][MAX];
int main(int argc, char* argv[])
{
// freopen("in.txt", "r", stdin);
//ios::sync_with_stdio(false); cin.tie(0);
int t = readIntLn(1, 5);
FOR(tt,0,t)
{
int n = readIntSp(1, 300);
int m = readIntLn(1, n * (n - 1) / 2);
FOR(i,0,n)
{
FOR(j,0,n)
D[i][j] = INF;
D[i][i] = 0;
}
set<PII> S;
FOR(i,0,m)
{
int u = readIntSp(1, n);
int v = readIntSp(1, n);
int w = readIntLn(1, 1000000);
S.insert(MP(u, v));
S.insert(MP(v, u));
--u;--v;
D[u][v] = D[v][u] = w;
}
VI F(n);
FOR(i,0,n)
{
F[i] = readInt(1, INF, (i + 1 < n ? ' ' : '\n'));
}
int p = readIntSp(1, n);
int q = readIntLn(1, n);
--p; --q;
assert(SZ(S) == 2 * m);
FOR(k,0,n)
FOR(i,0,n)
FOR(j,0,n)
D[i][j] = min(D[i][j], D[i][k] + D[k][j]);
assert(D[p][q] < INF);
FOR(i,0,n)
FOR(j,0,n)
D[i][j] *= F[i];
FOR(k,0,n)
FOR(i,0,n)
FOR(j,0,n)
D[i][j] = min(D[i][j], D[i][k] + D[k][j]);
cout << D[p][q] << endl;
}
assertEof();
cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl;
}
Time Complexity=O(N^3)
Space Complexity=O(N^2)
CHEF VIJJU’S CORNER
Why is the new Graph G` directed?
Undirected graph means that cost from Node u to v is same as cost from v to u! But since cost of petrol can be different at u and v, then this property does not hold! Hence, we break the undirected edge from u to v to 2 parts-
- Directed Edge from u to v with weight W1
- Directed edge from v to u with weight W2
This lets us capture every required essence of the question and a shortest path on this directed graph lets us find the final answer.
2.What would you do if the cost of petrol can go negative? Will the same solution of editorial work? Why/Why not?
In the new Graph G`, we used Floyd Warshall. Can we instead use something more optimal like Dijkstra to find shortest path there?
If edge weights are not negative, Dijkstra should work.
Tester's Notes
Find the shortest paths between each pair of vertices (Floyd algo).
Create new directed full graph where edge from v to u has length cost[v] * shortest_distance(v, u). That means we are going from v to u using petrol from v.
Run Floyd algo again on this graph to find the shortest path between p and q.
