Answer to Question #212294 in C for Raj

Question

You are given a roadmap of a country consisting of N cities and M roads. Each city has a traffic light. The traffic light has only 2 colors, Green and Red. All the traffic lights will switch their color from Green to Red and vice versa after every T seconds. You can cross a city only when the traffic light in the city is Green. Initially, all the traffic lights are Green. At a city, if the traffic light is Red, you have to wait for it to switch its color to Green. The time taken to travel through any road is C seconds. Find the minimum amount of time (in seconds) required to move from city 1 to city N.

It is guaranteed that the given roadmap will be connected. Graph won't contain multiple edges and self loops.

Input Format

The first line contains 4 space-separated integers, N (1 <=N<10³). M (N-1M <= (N(N-1)/2), T (1 <=T <=10³) and C (1<<C<=10³). Next M lines contain two integers each, U and V denoting that there is a bidirectional road between U and V.

Answer 1

#include <stdio.h>
/*
You are given a roadmap of a country consisting of N cities and M roads. 
Each city has a traffic light. The traffic light has only 2 colors, Green and Red. 
All the traffic lights will switch their color from Green to Red and vice versa after every T seconds. 
You can cross a city only when the traffic light in the city is Green. Initially, all the traffic lights are Green. 
At a city, if the traffic light is Red, you have to wait for it to switch its color to Green. 
The time taken to travel through any road is C seconds. 
Find the minimum amount of time (in seconds) required to move from city 1 to city N.


It is guaranteed that the given roadmap will be connected. Graph won't contain multiple edges and self loops.
Input Format
The first line contains 4 space-separated integers, N (1 <=N<10³). 
M (N-1M <= (N(N-1)/2), T (1 <=T <=10³) and C (1<<C<=10³). 
Next M lines contain two integers each, U and V denoting 
that there is a bidirectional road between U and V.
*/


#include<iostream>
#include <bits/stdc++.h>
#include<vector>
#include<map>
using namespace std;
#define lng long long int


vector<int> graph[1001];
vector<pair<lng,vector<lng>>> pt;


void helper(lng start,lng end,lng visited[],vector<lng> rs,lng w){
   rs.push_back(start);
   if(start == end){
       pt.push_back({w*(rs.size()-1),rs});
       return;
   }
   for(auto u : graph[start]){
       if(visited[u] == 0){
          visited[start] = 1;
          helper(u,end,visited,rs,w);
          visited[start] = 0;
       }
   }
}


int main()
{
    lng n,m,t,c,u,v;
    cin>>n>>m>>t>>c;
    while(m--){
        cin>>u>>v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    
    if(n == 1)
    cout<<0<<endl;
    else if(n == 2)
    cout<<t<<endl;
    else{
        vector<lng> rs;
        lng w = c;
        lng visited[n+1] = {0};
        helper(1,n,visited,rs,w);
        if(pt.size() == 0)
        cout<<-1<<endl;
        else{
        sort(pt.begin(),pt.end());
        lng te = 0;
        lng nt = 0;
        for(int i=1;i<pt[0].second.size();i++){
            te += c + (nt-te);
            while(nt < te)
            nt += t;
        }
        cout<<endl<<"Minimum time : "<<te<<" seconds"<<endl;
        }
    }
    return 0;
}