PROBLEM LINK:
Author: arnie8991
Tester @dshahid3801
Editorialist: arnie8991
DIFFICULTY:
Medium
PREREQUISITES:
Graphs, Dijkstra
EXPLANATION:
In this problem in order to assess whether the maze designed by Cobb passes or fails, we need to figure out the shortest path that a person can take to get in and out of the maze. But he can use any of the entry and exit points in the whole and maze and thats what we are required to find. If we find that the path between any of the entry and exit points is less than K then the maze fails.
Intuitively one can think that this problem can be solved using Floyd-Warshall’s All source shortest pair Path algorithm, but that algorithm has a runtime of O(N^3) and if we go over the constraints we will find that N goes up till 1000, hence we need something faster. So for his scenario, the most optimal approach will be to solve it using Dijkstra. Hence for all the entry and exit pairs, we need to find the shortest path connecting that pair. Since there are at most 100 entry and exit points, then out Algorithm will have a runtime complexity of O(A*(N^2 + A)) which should suffice.
Time Complexity : O(A*(N^2 + A)), where N is the number of vertices and A is the number of entry and exit points.
Space complexity : O(N^2 + A)
If one uses Priority Queue for Dijkstra then the complexity further reduces down and becomes: O(A*(NlogE + A)), where E is the number of edges in the graph.
SOLUTIONS:
[details="Setter’s Solution]
import java.util.*;
class Main{
public static int minDistance(int dist[], Boolean sptSet[], int n)
{
int min = Integer.MAX_VALUE, min_index = -1;
for (int v = 1; v <= n; v++)
if (sptSet[v] == false && dist[v] <= min) {
min = dist[v];
min_index = v;
}
return min_index;
}
public static int[] dijkstra(int graph[][], int src, int n)
{
int dist[] = new int[n+1];
Boolean sptSet[] = new Boolean[n+1];
for (int i = 1; i <= n; i++) {
dist[i] = Integer.MAX_VALUE;
sptSet[i] = false;
}
dist[src] = 0;
for (int count = 1; count <= n - 1; count++) {
int u = minDistance(dist, sptSet, n);
sptSet[u] = true;
for (int v = 1; v <= n; v++)
if (!sptSet[v] && graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE && dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
return dist;
}
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int e = sc.nextInt();
int a = sc.nextInt();
int[] eex = new int[a];
int graph[][] = new int[n+1][n+1];
for(int i = 0; i <= n; i++){
for(int j = 0; j <= n ;j++){
graph[i][j] = 0;
}
}
for(int i = 0; i < a; i++){
eex[i] = sc.nextInt();
}
// Initialize list for every node
for(int i = 0; i < e; i++ ){
int u = sc.nextInt();
int v = sc.nextInt();
int w = sc.nextInt();
graph[u][v] = w;
graph[v][u] = w;
}
int shortest = Integer.MAX_VALUE;
for(int i : eex){
int dist[] = dijkstra(graph, i, n);
for (int j : eex){
if (i!=j){
shortest = Math.min(shortest, dist[j]);
}
}
}
if (shortest >= k)
System.out.println("PASS");
else
System.out.println("FAIL");
}
}
Tester’s solution:
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long int
#define ll long long int
#define vi vector<int>
#define vvi vector<vector<int>>
#define pll pair<ll, ll>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vpll vector<pair<ll,ll>>
#define umap unordered_map
#define uset unordered_set
#define all(c) c.begin(), c.end()
#define maxarr(A) *max_element(A, A+n)
#define maxvec(v) *max_element(all(v))
#define present(map,elem) map.find(elem)!=map.end()
#define lb(v,elem) lower_bound(all(v),elem)
#define ub(v,elem) upper_bound(all(v),elem)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define For(i,a,b) for(int i=a; i<b; ++i)
#define rep(i,a,b) for(ll i=a; i<b; ++i)
#define debug(v) for(ll i=0; i<v.size(); i++) cout<<v[i]<<" "; cout<<endl;
#define debugn(v,n) for(ll i=0; i<n; i++) cout<<v[i]<<" "; cout<<endl;
#define mod 1000000007
#define INF 1000000000
#define endl '\n'
vector<vector<pair<int, int>>> adj(1005);
vi dijkstra(int s, int n) {
vi d(n+1,INF);
vi p(n+1,-1);
d[s] = 0;
using pii = pair<int, int>;
priority_queue<pii, vector<pii>, greater<pii>> q;
q.push({0, s});
while (!q.empty()) {
int v = q.top().second;
int d_v = q.top().first;
q.pop();
if (d_v != d[v])
continue;
for (auto edge : adj[v]) {
int to = edge.first;
int len = edge.second;
if (d[v] + len < d[to]) {
d[to] = d[v] + len;
p[to] = v;
q.push({d[to], to});
}
}
}
//debug(d)
return d;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
//freopen("1.in","r",stdin);
int n,k,e,m;
cin>>n>>k>>e>>m;
vi a(m);
For(i,0,m) cin>>a[i];
For(i,0,e){
int x,y,w;
cin>>x>>y>>w;
adj[x].push_back({y,w});
adj[y].push_back({x,w});
}
int ans = INF;
for(int x : a){
vi d = dijkstra(x,n);
for(int y : a){
if(x!=y)
ans = min(ans, d[y]);
}
}
if(ans>=k) cout<<"PASS"<<endl;
else cout<<"FAIL"<<endl;
return 0;
}