Wednesday, June 24, 2009

47. Roads

Roads:

N cities named with numbers 1 ... N are connected with one-way roads. Each road has two parameters associated with it: the road length and the toll that needs to be paid for the road (expressed in the number of coins). Bob and Alice used to live in the city 1. After noticing that Alice was cheating in the card game they liked to play, Bob broke up with her and decided to move away - to the city N. He wants to get there as quickly as possible, but he is short on cash. We want to help Bob to find the shortest path from the city 1 to the city N that he can afford with the amount of money he has.
Input

The input begins with the number t of test cases. Then t test cases follow. The first line of the each test case contains the integer K, 0 <= K <= 10000, maximum number of coins that Bob can spend on his way. The second line contains the integer N, 2 <= N <= 100, the total number of cities. The third line contains the integer R, 1 <= R <= 10000, the total number of roads. Each of the following R lines describes one road by specifying integers S, D, L and T separated by single blank characters : S is the source city, 1 <= S <= N D is the destination city, 1 <= D <= N L is the road length, 1 <= L <= 100. T is the toll (expressed in the number of coins), 0 <= T <= 100 Notice that different roads may have the same source and destination cities.
Output

For each test case, output a single line contain the total length of the shortest path from the city 1 to the city N whose total toll is less than or equal K coins. If such path does not exist, output -1.
Example

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

Output:
11
-1
Posted by Anurag at 5:51 PM

1 comments:

Anurag said...

Following c code works well:
/*

The algorithm does a breadth-first search in a graph
always choosing the cheapest options first.
Vertices that need to be visited are stored in a sorted
list (sorted by the price needed to get to that vertex).
algorithm starts by inserting the starting node in the
list.
One step of the algorithm does:
- take the first element in the list - the next cheapest
path in the graph
- visit the vertex defined by that element
- if the vertex was already visited then:
- if the preavious distance was smaller - do nothing
(because we traverse tgraph in such way that
the preavious cost was also smaller)
- else put all the neighbours on the list and update
distance
Algorithm stops when the list empties.

*/

#include
#include

#define MAX_CITIES 100
#define LIST_SIZE 3000
#define A_LOT 30000
#define NO -1

int number_of_coins,number_of_cities,number_of_roads;
int were[MAX_CITIES];

typedef struct {
int money,node,distance;
} car;

car list[LIST_SIZE];
int head;

typedef struct {
char from,to,cost,length;
} road;

road roads[MAX_CITIES * MAX_CITIES];



void read_input(void)
{
int i;
int c1,c2,c3,c4;





scanf("%d %d %d",&number_of_coins,&number_of_cities,&number_of_roads);

for (i = 0;i < number_of_cities;++i)
were[i] = NO;

for (i = 0;i < number_of_roads;++i)
{
scanf("%d %d %d %d",&c1,&c2,&c3,&c4);;

roads[i].from = c1 - 1;
roads[i].to = c2 - 1;
roads[i].length = c3;
roads[i].cost = c4;
}


}

void initlist(void)
{
list[0].money = A_LOT;
list[0].node = A_LOT;

head = 1;

return;
}

int empty(void)
{
return (head == 1);
}

void insert(car a)
{
int i,j;

i = head;

while (list[i - 1].money <= a.money)
{
if (list[i - 1].node == a.node)
{
if (list[i - 1].distance <= a.distance)
return;

if ((list[i - 1].money == a.money) &&
(a.distance < list[i - 1].distance))
{
list[i - 1] = a;
return;
}
}

--i;
}

if (i == head)
{
list[i] = a;
++head;

return;
}

for (j = head;j > i;--j)
list[j] = list[j - 1];

list[i] = a;
++head;

return;
}

void first(car *a)
{
*a = list[--head];

return;
}

// compare function for "qsort"

int sort_func(const void *a,const void *b)
{
if (((road *) a)->from > ((road *) b)->from)
return 1;

if (((road *) a)->from < ((road *) b)->from)
return -1;

return 0;
}

void solve(void)
{
int i,j;
int start[MAX_CITIES];
car t,tmp;

qsort(roads,number_of_roads,sizeof(roads[0]),sort_func);

j = 0;

for (i = 0;i < number_of_cities;++i)
{
while ((roads[j].from < i) && (j < number_of_roads))
++j;
if (j == number_of_roads)
--j;
start[i] = j;
}

t.money = 0;
t.node = 0;
t.distance = 0;

initlist();

insert(t);

while (!empty())
{
first(&t);

if ((were[t.node] == NO) || (t.distance < were[t.node]))
{
were[t.node] = t.distance;

for (i = start[t.node];roads[i].from == t.node;++i)
if (t.money + roads[i].cost <= number_of_coins)
{
tmp.money = t.money + roads[i].cost;
tmp.node = roads[i].to;
tmp.distance = t.distance + roads[i].length;

insert(tmp);
}
}
}

}

void write_output(void)
{
printf("%d\n",were[number_of_cities - 1]);
}

int main(void)
{
int cases;
scanf("%d",&cases);
while(cases-->0){
read_input();

solve();

write_output();
}
return 0;
}

June 24, 2009 5:55 PM

Post a Comment

Subscribe to: Post Comments (Atom)