code the below problem please

[ria1]

// please can anyone provide a Code of this problem.

Janet is in an Uber on her way to an interview. The driver promises to take her to the venue as soon as possible. The driver is aware
that:-
-There are 'n' junctions in the city of Mumbai, numbered from '1' to 'n'.
-Janet's interview location is at junction 'n'. They are initially at junction '1'.
-There are 'm' bidirectional roads connecting some pairs of junctions, each one requiring some amount of time to pass through it.

At every junction, there are traffic lights denoting whether they are allowed to go further or to wait. Traffic lights have two colors,
'red' and 'green'. The driver can commute through junctions based on these conditions:
1. At any junction, if the traffic signal's light is green, then they can go immediately, otherwise, they have to wait until traffic signal
becomes green.
2. Traffic signal changes its color every 'k' seconds of time at all junctions simultaneously.

Initially, at the '0th' second, all traffic lights have changed to green color at all the junctions. If the cab driver reaches a junction at a second when the traffic light changes its color, then he sees the traffic light after the change.
Can you help the driver determine the least amount of time needed to reach the interview location?
Complete the function leastTimeToInterview which takes in three integers n,k and m and returns the least amount of time
needed to reach the interview location, in seconds. You need to take the information about the roads from the standard input. They
will be specified in 'm' lines, as described in the input format section below.

Input Format:-

-The first line contains an integer 'n', the number of junctions.
-The second line contains an integer 'k' denoting the time taken by a signal to change its color.
-The third line contains an integer 'm' denoting the number of roads.
-The next 'm' lines describe the roads. Each consist of three space-separated integers 'i','j' and 't' where 'i' and 'j' denotes a road between two junctions and 't' denotes time required to travel through it.

Constraints-:
- 1<= n <= pow(10,4)
- 1<= k <= pow(10,2)
- 1<= m <= pow(10,5)
- 1<= i,j <= n
- 1<= t <= pow(10,3)

- There can be self-loops, i.e., roads connecting the same pair of junctions.
- There is at least one path from junction '1' to junction 'n'.

Output Format-:

Print a single integer denoting the shortest amount of time required to reach junction 'n'.

Sample Input 0
7
4
7
1 2 3
2 3 1
1 4 4
4 6 7
7 5 2
3 5 1
4 5 5

Sample Output 0
11


Explanation 0-

- Junction number 1: The cab driver can visit any of the adjacent junctions. He chooses to visit junction 2. Since the traffic signal is
'green' at the '0th' second, He can visit junction 2 which takes 3 seconds.
- Junction number 2: The traffic signal is still 'green' since traffic signals change color every '4' seconds. The cab driver now chooses
to visit junction '3' which takes '1' second, and we are now at the '4th' second.
- Junction number 3: 4 seconds have passed, and the traffic signal has already become 'red'. They have to wait for 4 more seconds
until the signal again becomes 'green'.
- Junction number 5: The cab takes the route to junction 5 which takes 1 second. So far, 9 seconds have passed.
- Junction number 7: The traffic signal is still 'green' and the cab can go to junction 7. It takes 2 seconds to reach junction 7.

In total, it takes 11 seconds to go from junction 1 to junction 7 . It can be shown that this is the minimum amount of time possible.


#include <bits/stdc++.h>
using namespace std;

// Complete the leastTimeToInterview function below.
long leastTimeToInterview(int n, int k, int m) {

// Return the least amount of time needed to reach the interview location in seconds.
}

int main()
{
ofstream fout(getenv("OUTPUT_PATH"));
int n;
cin >> n;

cin.ignore(numeric_limits<streamsize>::max(), '\n');
int k;
cin >> k;

cin.ignore(numeric_limits<streamsize>::max(), '\n');
int m;
cin >> m;

cin.ignore(numeric_limits<streamsize>::max(), '\n');
long result = leastTimeToInterview(n, k, m);
fout << result << "\n";
fout.close();
return 0;
}

[jonnin]

Ok. I try to live and let live, but did you really hijack another thread to link to this one because you waited a whole hour for an answer to a fairly complex question and got impatient? Please don't do that. Wait for it, someone will help if they can, when they can.

This question takes some time to digest ... about all I see so far is it looks like a graph theory question, some of which you can solve with just some hand-waving and vectors and others which require a full graph representation. But I am not 100% sure of what we have here, there may be some clever or simple thing that solves it without all that mess.

What do you have so far? Besides that fairly generic and unrelated to the meat of the problem code, I mean? Honestly, I don't even want to see your code, yet, I would rather hear you tell me how you plan to solve the problem, what algorithm, what data structure, etc. Coding comes much later.

[ria1]

i am very weak in the graph part of the Data Structure , so i am unable to code it.
So please can you code this problem.

[jonnin]

how will me doing it for you make you better at doing graphs? (It won't, you will still be bad at them, and I will get a review of something I haven't looked at since college and don't really care much about).

So I will ask again... how will you solve this problem? Pretend you have in hand a working datastructure that you can just use, once you figure out HOW to use it. Talk through the approach you need. Start small. You have a good idea ... a file reader is one necessary part of the whole. What are the other parts?

I am just going to tell you right now that I won't do it for you. I will help, once you decide to own it and do it yourself.

[tpb]

A very simple modification of Dijkstra's shortest path algorithm solves it handily. Give it a try.

[closed account 1TD80pDG]

@tpb
test case :
8 3 10
1 2 3
1 3 2
2 4 4
3 4 4
3 5 6
4 6 2
5 6 1
5 7 7
6 8 5
7 8 8

the output of this test cae is 13 but my code is giving 16.
when we need to wait for trafic singnal.
i mean for every divigible of k we need to add k

if(dist[v]%k==0&&dist[v]>0)
                   dist[v]=dist[v]+k;

how can i modify this to get deisred output ?

[tpb]

Consider the following table based on a traffic light period of 3 seconds:

t  /3  %3
0   0   0   green
1   0   1   green
2   0   2   green
3   1   0   red
4   1   1   red
5   1   2   red
6   2   0   green
7   2   1   green
8   2   2   green
9   3   0   red

Note that if you hit an intersection at time 6, the light is green so there is no delay. If you hit at time 5, you need to wait 1 second.

However, the input you gave looks like it should be 13 to me.

1 --> 3     2   green
3 --> 4     6   green
4 --> 6     8   green
6 --> 8    13   DONE

[closed account 1TD80pDG]

@tpb thanks, but I don't pass test case 3rd. any suggestion for it.

[tpb]

I don't know what test case 3 is and I have no idea what your code looks like.

[closed account 1TD80pDG]

here is part of code.

where D[v] is sum of cost of path when visiting new node.

double division;
                
                 division= (D[v])/(k);
                
                if(long(division)%2!=0 )  
                {  
                    
                  D[v]=D[v]+k-D[v]%k;
                }
                

is it a right condition or something needed to modify. when the signal is red then we need to add k-D[v]%k.

[tpb]

You don't need a floating point variable. Integer division will do.

    if (v != goal && D[v] / k % 2 == 1)
        D[v] += k - D[v] % k;

Note that you must ensure that v is not the goal (the final node) since in that case you don't care if the light is red. That's probably what you're missing.

[closed account 1TD80pDG]

@tpb finally, you saved my life, huge thanks.

[ria1]

@ipg
Can you please PM me your code.

[tpb]

you saved my life, huge thanks

You're welcome. Good job!
It's up to you, but I wouldn't PM someone your code who never even tried to solve it themselves.

[jabbar1701]

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

ll g[10005][10005];
vector<bool> visited(10005,0);
vector<ll> path(10005),ans;
ll path_index=0;
ll m,k;
void clr()
{
for(ll i=0; i<=m; i++)
for(ll j=1; j<=m; j++)
g[i][j]=0;
}

void calc(ll u, ll d)
{
visited[u] = true;
path[path_index] = u;
path_index++;
if(u==d)
{ ll t=0;
for(ll i=1; i<path_index; i++)
{ if(t%(2*k)>=k && t%(2*k)<=2*k-1)
t+=2*k-(t%(2*k));
t+=g[path[i]][path[i-1]];
}
ans.pb(t);
}
else
{
for(ll i=1; i<=m+1; i++)
if(g[u][i]!=0 && visited[i]!=1)
calc(i,d);
}
path_index--;
visited[u]=0;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll n,a,b,x,i;
cin>>n>>k>>m;
clr();
for(i=1; i<=m; i++)
{
cin>>a>>b>>x;
g[a][b]=x;
g[b][a]=x;
}
calc(1,n);
sort(ans.begin(),ans.end());
cout<<ans[0]<<endl;
return 0;
}

I am getting segmentation fault.Can anyone plz help