Answer to Question #242079 in C for Pradosh

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

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;
typedef long long int lng;

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;
}