PROBLEM LINK:
PRACTICE
Editorialist: Avishake Maji
DIFFICULTY:
MEDIUM
PREREQUISITES:
Graphs
PROBLEM:
Chef and his team after working for making years finally succeeded in building up a plagiarism detector. But when Chef is taking a nap the warning alarm suddenly rings. Since Chef is the only one who is near to the base where the plagiarism detector is fitted so he has to fix the problem before their detector destroys.
There are different paths from chef’s base to the target base but chef has to take the shortest path and fix the problem before the timer T(min)T(min) goes to 00. Chef knows the map of the base and the distance between two consecutive bases. Chef needs your help to find whether he will reach in time or not. If he is able to reach in time print “Successful” else print “Unsuccessful”.
There are N number of bases. Chef lives in base 11 and he has to reach the base N. The speed at which chef’s run is given in S(meter/min)S(meter/min). Remember chef runs at a uniform speed throughout. U and V denote any pair of bases and W(meter)W(meter) is the distance between U and VV.
EXPLANATION:
Here in this problem, we have first find the shortest distance from Base 1 to Base N i.e target base. We can use Dijkstra’s algorithm which solves the single-source shortest path problem. After
finding the shortest path, we have to calculate time.
SOLUTION:
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
ll mindistance(bool *vis,ll *dist,ll n){
ll minval=INT_MAX;
ll min_ind;
for(ll i=0;i<n;i++){
if(dist[i]<=minval&&vis[i]==false){
minval=dist[i];
min_ind=i;
}
}
return min_ind;
}
ll calShortestDistance(vector<vector<ll>>&adj,ll n){
ll *dist=new ll[n];
bool *visited=new bool[n];
for(ll i=0;i<n;i++)
{
visited[i]=false;
dist[i]=INT_MAX;
}
dist[0]=0;
for(ll i=0;i<n-1;i++){
ll u=mindistance(visited,dist,n);
visited[u]=true;
for(int j=0;j<n;j++){
if(adj[u][j]&&visited[j]==false&&dist[u]!=INT_MAX&&dist[u]+adj[u][j]<dist[j]){
dist[j]=dist[u]+adj[u][j];
}
}
}
return dist[n-1];
}
int main(){
ll n,e,t,speed;
cin>>n>>e>>t>>speed;
ll u,v,w;
vector<vector<ll>>adj(n,vector<ll>(n,0));
for(ll i=0;i<e;i++)
{
cin>>u>>v>>w;
adj[u-1][v-1]=w;
adj[v-1][u-1]=w;
}
ll shortest_dist=calShortestDistance(adj,n);
double cal_time=(1.0*shortest_dist)/speed;
if(cal_time<=t)
cout<<"Successful";
else
cout<<"Unsuccessful";
cout<<"\n";
}