OJ Board

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

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

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

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