Given K descriptions for bus line paths that exists to lead students between N campuses. What is the minimum cost that a student will have to goes from campus 1 to campus N ?
The itinerary of each path L is a sequence of |L|( ≥ 2 ) campuses {C1, C2, ..., CL}, and each line has only one bus, which passes by all campuses of the line, following the itinerary order, stopping in each of them and making a U-turn whenever it reaches an endpoint of the itinerary, reversing the itinerary order. The transport pass costs 1,ドル and has to be paid by the passenger while getting onto the bus, no matter the time the passenger is going to stay in it.
Input:
The first input line consists of two integers N and K (2 ≤ N ≤ 10^4, 1 ≤ K ≤ 10^3), which represent respectively the number of campuses and the number of public transport lines created by UFFS. Each one of the K input lines following describes a transport line L and consists of the integer |L| (2 ≤ |L| ≤ 10^2) followed by the |L| identifiers Ci (1 ≤ Ci ≤ N, 1 ≤ i ≤ |L|) of the campuses by which the ship passes, wherein C1 and C|L| are the endpoints of L. For every campus A and every campus B it is guaranteed that it is possible to go from A to B.
Output:
Output the minimum cost to go from campus 1 to campus N.
I'm getting time limit exceeded on the judge that has [this problem][1]this problem. How can i make this solution faster ?
[![Bus lines][2]][2]Bus lines
For this case the minimum cost is 2; [1]: http://www.urionlinejudge.com.br/repository/UOJ_1908_en.html [2]: https://i.sstatic.net/ZC48H.jpg
Given K descriptions for bus line paths that exists to lead students between N campuses. What is the minimum cost that a student will have to goes from campus 1 to campus N ?
The itinerary of each path L is a sequence of |L|( ≥ 2 ) campuses {C1, C2, ..., CL}, and each line has only one bus, which passes by all campuses of the line, following the itinerary order, stopping in each of them and making a U-turn whenever it reaches an endpoint of the itinerary, reversing the itinerary order. The transport pass costs 1,ドル and has to be paid by the passenger while getting onto the bus, no matter the time the passenger is going to stay in it.
Input:
The first input line consists of two integers N and K (2 ≤ N ≤ 10^4, 1 ≤ K ≤ 10^3), which represent respectively the number of campuses and the number of public transport lines created by UFFS. Each one of the K input lines following describes a transport line L and consists of the integer |L| (2 ≤ |L| ≤ 10^2) followed by the |L| identifiers Ci (1 ≤ Ci ≤ N, 1 ≤ i ≤ |L|) of the campuses by which the ship passes, wherein C1 and C|L| are the endpoints of L. For every campus A and every campus B it is guaranteed that it is possible to go from A to B.
Output:
Output the minimum cost to go from campus 1 to campus N.
I'm getting time limit exceeded on the judge that has [this problem][1]. How can i make this solution faster ?
[![Bus lines][2]][2]
For this case the minimum cost is 2; [1]: http://www.urionlinejudge.com.br/repository/UOJ_1908_en.html [2]: https://i.sstatic.net/ZC48H.jpg
Given K descriptions for bus line paths that exists to lead students between N campuses. What is the minimum cost that a student will have to goes from campus 1 to campus N ?
The itinerary of each path L is a sequence of |L|( ≥ 2 ) campuses {C1, C2, ..., CL}, and each line has only one bus, which passes by all campuses of the line, following the itinerary order, stopping in each of them and making a U-turn whenever it reaches an endpoint of the itinerary, reversing the itinerary order. The transport pass costs 1,ドル and has to be paid by the passenger while getting onto the bus, no matter the time the passenger is going to stay in it.
Input:
The first input line consists of two integers N and K (2 ≤ N ≤ 10^4, 1 ≤ K ≤ 10^3), which represent respectively the number of campuses and the number of public transport lines created by UFFS. Each one of the K input lines following describes a transport line L and consists of the integer |L| (2 ≤ |L| ≤ 10^2) followed by the |L| identifiers Ci (1 ≤ Ci ≤ N, 1 ≤ i ≤ |L|) of the campuses by which the ship passes, wherein C1 and C|L| are the endpoints of L. For every campus A and every campus B it is guaranteed that it is possible to go from A to B.
Output:
Output the minimum cost to go from campus 1 to campus N.
I'm getting time limit exceeded on the judge that has this problem. How can i make this solution faster ?
For this case the minimum cost is 2;
Given K descriptions for bus line paths that exists to lead students between N campuses. What is the minimum cost that a student will have to goes from campus 1 to campus N ?
The itinerary of each path L is a sequence of |L|( ≥ 2 ) campuses {C1, C2, ..., CL}, and each line has only one bus, which passes by all campuses of the line, following the itinerary order, stopping in each of them and making a U-turn whenever it reaches an endpoint of the itinerary, reversing the itinerary order. The transport pass costs 1,ドル and has to be paid by the passenger while getting onto the bus, no matter the time the passenger is going to stay in it.
Input:
The first input line consists of two integersGiven NK anddescriptions for bus line paths that exists to lead students between KN (2 ≤ N ≤ 10^4, 1 ≤ K ≤ 10^3), which represent respectively the number of campuses and the number of public transport lines created by UFFS. Each one ofWhat is the K input lines following describesminimum cost that a transport linestudent will have to goes from campus 1 to campus N L and consists?
The itinerary of the integer |L|each path (2 ≤ |L| ≤ 10^2) followed by the is a sequence of |L| identifiers( ≥ 2 Ci) campuses (1 ≤ Ci ≤ N{C1, 1 ≤ i ≤ |L|)C2, ..., CL}, and each line has only one bus, which passes by all campuses of the campuses by whichline, following the ship passesitinerary order, wherein C1stopping in each of them and C|L| are the endpointsmaking a U-turn whenever it reaches an endpoint of Lthe itinerary, reversing the itinerary order. For every campus AThe transport pass costs 1,ドル and every campus B it is guaranteed that it is possiblehas to go from Abe paid by the passenger while getting onto the bus, no matter the time the passenger is going to Bstay in it.
Output:
Input:
The first input line consists of two integers N and K (2 ≤ N ≤ 10^4, 1 ≤ K ≤ 10^3), which represent respectively the number of campuses and the number of public transport lines created by UFFS. Each one of the K input lines following describes a transport line L and consists of the integer |L| (2 ≤ |L| ≤ 10^2) followed by the |L| identifiers Ci (1 ≤ Ci ≤ N, 1 ≤ i ≤ |L|) of the campuses by which the ship passes, wherein C1 and C|L| are the endpoints of L. For every campus A and every campus B it is guaranteed that it is possible to go from A to B.
Output the minimum cost to go from campus 1 to campus N.:
Output the minimum cost to go from campus 1 to campus N.
Given K descriptions for bus line paths that exists to lead students between N campuses. What is the minimum cost that a student will have to goes from campus 1 to campus N ?
The itinerary of each path L is a sequence of |L|( ≥ 2 ) campuses {C1, C2, ..., CL}, and each line has only one bus, which passes by all campuses of the line, following the itinerary order, stopping in each of them and making a U-turn whenever it reaches an endpoint of the itinerary, reversing the itinerary order. The transport pass costs 1,ドル and has to be paid by the passenger while getting onto the bus, no matter the time the passenger is going to stay in it.
Input:
The first input line consists of two integers N and K (2 ≤ N ≤ 10^4, 1 ≤ K ≤ 10^3), which represent respectively the number of campuses and the number of public transport lines created by UFFS. Each one of the K input lines following describes a transport line L and consists of the integer |L| (2 ≤ |L| ≤ 10^2) followed by the |L| identifiers Ci (1 ≤ Ci ≤ N, 1 ≤ i ≤ |L|) of the campuses by which the ship passes, wherein C1 and C|L| are the endpoints of L. For every campus A and every campus B it is guaranteed that it is possible to go from A to B.
Output:
Output the minimum cost to go from campus 1 to campus N.
Given K descriptions for bus line paths that exists to lead students between N campuses. What is the minimum cost that a student will have to goes from campus 1 to campus N ?
The itinerary of each path L is a sequence of |L|( ≥ 2 ) campuses {C1, C2, ..., CL}, and each line has only one bus, which passes by all campuses of the line, following the itinerary order, stopping in each of them and making a U-turn whenever it reaches an endpoint of the itinerary, reversing the itinerary order. The transport pass costs 1,ドル and has to be paid by the passenger while getting onto the bus, no matter the time the passenger is going to stay in it.
Input:
The first input line consists of two integers N and K (2 ≤ N ≤ 10^4, 1 ≤ K ≤ 10^3), which represent respectively the number of campuses and the number of public transport lines created by UFFS. Each one of the K input lines following describes a transport line L and consists of the integer |L| (2 ≤ |L| ≤ 10^2) followed by the |L| identifiers Ci (1 ≤ Ci ≤ N, 1 ≤ i ≤ |L|) of the campuses by which the ship passes, wherein C1 and C|L| are the endpoints of L. For every campus A and every campus B it is guaranteed that it is possible to go from A to B.
Output:
Output the minimum cost to go from campus 1 to campus N.