10039 - Railroads

[Red Scorpion]

Hi, I try to solve this problem but I really dont understand the input.

2 ->number of scenario
3 ->number of city
Hamburg
Frankfurt
Darmstadt
3 ->number of train
2 ->number of city.
0949 Hamburg
1006 Frankfurt
2
1325 Hamburg
1550 Darmstadt
2
1205 Frankfurt
1411 Darmstadt
0800
Hamburg
Darmstadt

When number of city > 2, what happen ?
3
0949 Hamburg
1006 Frankfurt
0800 London

ti more lines with a time and a city name, meaning that passengers can get on or off the train at that time at that city.

Please help me...

[Red Scorpion]

I still don't understand ... Can anyone help ... ?

[LittleJohn]

When number of city > 2, what happen ?
3
0949 Hamburg
1006 Frankfurt
0800 London

Hi, it's a schedule of train ti.
It means train ti will start at Hamburg at 9:49, and arrive Frankfurt at 10:06, and then London (8:00?!)...something like that..

[carneiro]

Does anybody have a NICE input for this problem ?

I'm tired of getting non-sense WAs

I've tried everything I could think of .. but still WA

[BiK]

I keep on getting TLE for this problem. I use Dijkstra's algorithm. I even implemented it using binary heap and still TLE.

Am I wrong using Dijkstra? Or should I use Fibonacci Heap? Can somebody post some critical test input data?

Thanks

[BiK]

I keep on getting TLE for this problem. I use Dijkstra's algorithm. I even implemented it using binary heap and still TLE.

Am I wrong using Dijkstra? Or should I use Fibonacci Heap? Can somebody post some critical test input data?

Thanks

[Whinii F.]

If you try to solve this problem with Dijkstra, You will have one instance of each city in each discrete time. So you can have at most 100 * 1000 = 100,000 vertices. Of course it is unlikely V can be that large, but it can be too critical.

So try modeling this problem as something other than a shortest path problem, since there are time flows in this problem...


To be specific, (and a bit spoiler) think about DP.
(Like the Spy problem in the Last World Finals..)

[Maniac]

For the needy, here some input with tricky or non-tricky cases:

Code: Select all

14
3
A
B
C
3
2
1200 B
1300 C
2
0800 A
0900 B
2
1000 A
1100 B
0700
A
C
4
D
C
A
B
3
3
0800 A
1400 D
1500 C
2
0700 A
0800 B
3
0810 B
0850 C
1423 D
0600
A
D
4
A
B
C
D
2
2
1349 A
1423 B
2
1745 C
1857 D
0800
A
D
4
A
B
C
D
2
3
0859 A
1200 C
1300 D
3
0959 A
1100 B
1201 C
0700
A
D
2
A
U
1
2
0800 A
1000 U
0801
A
U
2
A
U
0
0800
A
U
3
A
U
R
2
2
0800 A
1001 U
2
1000 U
1100 R
0700
A
R
2
A
U
3
2
0700 A
1000 U
2
0800 A
1100 U
2
0900 A
1200 U
0901
A
U
3
Hamburg
Frankfurt
Darmstadt
3
2
0949 Hamburg
1006 Frankfurt
2
1325 Hamburg
1550 Darmstadt
2
1205 Frankfurt
1411 Darmstadt
0800
Hamburg
Darmstadt
2
Paris
Tokyo
1
2
0100 Paris
2300 Tokyo
0800
Paris
Tokyo
0
0
2359
Lutjebroek
Utrecht
3
Hamburg
Frankfurt
Darmstadt
3
2
0949 Hamburg
1006 Frankfurt
2
1325 Hamburg
1550 Darmstadt
2
1205 Frankfurt
1411 Darmstadt
0800
Hamburg
Darmstadt
2
Paris
Tokyo
1
2
0100 Paris
2300 Tokyo
0800
Paris
Tokyo
0
0
2359
Lutjebroek
Utrecht

output from AC solution:

Code: Select all

Scenario 1
Departure 1000 A
Arrival   1300 C

Scenario 2
Departure 0800 A
Arrival   1400 D

Scenario 3
No connection

Scenario 4
Departure 0859 A
Arrival   1300 D

Scenario 5
No connection

Scenario 6
No connection

Scenario 7
No connection

Scenario 8
No connection

Scenario 9
Departure 0949 Hamburg
Arrival   1411 Darmstadt

Scenario 10
No connection

Scenario 11
No connection

Scenario 12
Departure 0949 Hamburg
Arrival   1411 Darmstadt

Scenario 13
No connection

Scenario 14
No connection

Good luck! Erik

[coderaka]

Help me.
Thx.

[lonelyone]

Help me.
Thx.

Yes, did someone solve this problem by DP?
Please give us some hint.

Or may you use Dijkstra, please teach us how to model this problem.
I have no idea completely, so please descrip your ideas in detail.

Thanks a million.

[Solaris]

Hi all,

I have been gettin TLE in this problem for quite a long time now.
My solution is as follows:

1. I have created a graph with Cities as Vertices and Train Routes as edges.

2. I maintain an array bestDepTime[][]
bestDepTime[j] contains "If city(i) can be reached in time(j) then the best i.e. the latest Departure Time possible"

To me the complexity can be at best the size of the array bestDepTime .. I absolutely have no idea why I should get TLE I am ready to get WA though.

Hope someone can provide with an IO or reason for my TLE... thnx in advance

Code: Select all

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>

const int cmax = 105;
const int tmax = 24 * 60 + 5;

using namespace std;

struct Route
{
	int arrTime;	//Arrival Time in dest city
	int depTime;	//Departure from the current city
	int dest;		//Destination

	bool operator<(const Route &ob) const
	{
		if(depTime != ob.depTime)
			return depTime > ob.depTime;
		
		return arrTime < ob.arrTime;
	}
};

vector<Route> tList[cmax];
int nRoute[cmax];

int cVisit[cmax];
int bestDepTime[cmax][tmax];

int nCity, nTrain;
int src, dest, startTime;


void generateRoute(int currCity, int arrTime, int depTime)
{
	int i;

	//If the current city was reached with an EARLIER i.e. BETTER arrival time
	//Then the departure time for that arrival also is >= current depTime
	//Hence we can ignore this case
	if(cVisit[currCity] <= arrTime)
		return;

	cVisit[currCity] = arrTime;

	//If the current city is reached with this arrival time
	//then it is guaranteed that it was reached with a LATER i.e. BETTER depTime
	//As we are calling the functions with a decreasing order of departure time
	if(bestDepTime[currCity][arrTime] != -1)
		return;

	bestDepTime[currCity][arrTime] = depTime;

	for(i=0; i<nRoute[currCity]; i++)
	{
		if(tList[currCity][i].depTime >= arrTime)
			generateRoute(tList[currCity][i].dest, tList[currCity][i].arrTime, depTime);
		else
			break;
	}
}


int main(void)
{
	int i, j;

	int nTest, tst;

	map<string, int> cityNum;

	string currCity, prevCity;
	char cityName[100];

	Route rt;

	int frm, to, arrTime, depTime;


#ifndef ONLINE_JUDGE
	freopen("d:/programs/input/10039.txt", "r", stdin);
#endif

	scanf("%d", &nTest);

	for(tst=1; tst<=nTest; tst++)
	{
		scanf("%d", &nCity);

		for(i=0; i<nCity; i++)
		{
			scanf("%s", cityName);
			cityNum[cityName] = i;
		}

		scanf("%d", &nTrain);

		memset(nRoute, 0, sizeof(nRoute));

		for(i=0; i<nTrain; i++)
		{
			scanf("%d", &j);

			scanf("%d %s", &depTime, cityName);
			prevCity = cityName;
			frm = cityNum.find(prevCity)->second;

			j--;

			while(j--)
			{
				scanf("%d %s", &arrTime, cityName);
				currCity = cityName;

				to = cityNum.find(currCity)->second;

				rt.arrTime = arrTime / 100 * 60 + arrTime % 100;
				rt.depTime = depTime / 100 * 60 + depTime % 100;
				rt.dest = to;

				tList[frm].push_back(rt);
				nRoute[frm]++;

				prevCity = currCity;
				depTime = arrTime;
				frm = to;
			}
		}


		scanf("%d", &startTime);
		startTime = startTime / 100 * 60 + startTime % 100;

		src = dest = -1;

		scanf("%s", cityName);
		prevCity = cityName;
		src = cityNum.find(prevCity)->second;

		scanf("%s", cityName);
		currCity = cityName;
		dest = cityNum.find(currCity)->second;

		if(src < 0 || dest < 0)
		{
			printf("Scenario %d\n", tst);
			printf("No connection\n\n");
			continue;
		}
		
		for(i=0; i<nCity; i++)
			sort(tList[i].begin(), tList[i].end());


		//Initialization
		memset(bestDepTime, -1, sizeof(bestDepTime));
		memset(cVisit, 127, sizeof(cVisit));
		cVisit[src] = -1;
		
		for(i=0; i<nRoute[src]; i++)
		{
			if(tList[src][i].depTime >= startTime)
				generateRoute(tList[src][i].dest, tList[src][i].arrTime, tList[src][i].depTime);
			else
				break;
		}

		for(i=0; i<tmax; i++)
		{
			if(bestDepTime[dest][i] != -1)
			{
				arrTime = i;
				depTime = bestDepTime[dest][i];
				break;
			}
		}
		
		//Output
		printf("Scenario %d\n", tst);

		if(i >= tmax)
			printf("No connection\n\n");
		else
		{
			depTime = depTime / 60 * 100 + depTime % 60;
			arrTime = arrTime / 60 * 100 + arrTime % 60;

			printf("Departure %04d %s\n", depTime, prevCity.c_str());
			printf("Arrival   %04d %s\n\n", arrTime, currCity.c_str());
		}

		cityNum.clear();

		for(i=0; i<nCity; i++)
			tList[i].clear();
	}
	
	return 0;
}

[ashutoshmehra]

Hello everyone,

After many WAs and reworking my code many times, I am still unable to see where the bug lies in my code. I've tested my program with all the various test-cases in this thread (and some of my own), and I get correct result.

So, finally, I decided to request some clarification regarding the nature of the input -- in particular the train schedules.
1. Are the train stop times guaranteed to be in ascending order? If not, I think I'll need to sort them.
2. Can the times in the train schedules "wrap around" -- that is, something like:
2300 A
0000 B
0100 C
If so, how are we supposed to handle such an input?
3. Whatever, the "earliest start time" specified in the input, Jill must reach the destination by 2359 latest. Is that right? Thus, Jill can never take a train that "wraps around" midnight (like a train from A to C in the schedule above)?
4. The times are all in HHMM format and that 0 <= HH < 24 and 0 <= MM < 60. Is that right?

People who have got AC on this one, could you please confirm my understanding, or correct it?
Also, if some one can share any edge/tricky cases aside from the ones already posted, it might help me figure out the bug in my program.

Thanks!

[Articuno]

I am not sure how to solve this problem. Can anyone tell me about a general approach? Is it possible to solve this problem with bfs or dijkstra? Someone reply please... thanks in advance

[Obaida]

I think BFS should solve this.
But I am very much confused with the problem description.
Any one please help me

[Neil]

This problem makes no sense. I was testing random cases with the UVA toolkit, and I learned that it's wrong to assume that Jill can't go back in time.
For this case

Code: Select all

1
10
A
B
C
D
E
F
G
H
I
J
5
6
0072 B
1233 E
1975 F
0531 G
1223 I
0494 J
3
0661 B
1477 I
1602 J
4
1034 F
0567 G
1618 I
1218 J
8
0582 C
0667 D
1563 E
0870 F
1419 G
0840 H
1406 I
1200 J
8
0176 B
1939 C
1032 E
0461 F
0773 G
0895 H
1299 I
0868 J
389
C
G

the output is
Scenario 1
Departure 1939 C
Arrival 0531 G

Is this correct? Can Jill really arrive before she departs?