USACO OPEN07 Problem 'bparty' Analysis
by Richard Ho
We want to calculate the shortest time it takes for farm X to go to each farm.
We can do this by using a single-source shortest path algorithm called
Dijkstra. The algorithm works as follows. We start out with nothing marked as
reachable except for farm X. We mark all farms as unvisited. Distance to each
farm starts out as infinite, and distance to farm X is 0 (takes no time to go
there). Then while there are still unvisited farms that are reachable, find the
closest (smallest distance) reacheable, unvisited farm and visit that farm.
When we visit a farm Y, we mark farm Y as visited, and mark all neighbors of
farm Y as reacheable with distance equal to distance to Y + the time it takes
to go there, unless it already has a smaller distance. We keep doing this until
there are no more reacheable, unvisited farms. What we desire is precisely the
distances to each farm after the procedure complete. For more information, you
can search about Dijkstra's shortest path algorithm online, or refer to Section
2.4 in the training pages.
Below is a solution from Rob Kolstad that may or may not use this method above.
#define MAXFARMS 1000
#include <stdio.h>
#include <strings.h>
struct road_f {
int r_dstfarm; /* destination farm */
unsigned char r_time; /* time to traverse */
struct road_f *r_next; /* more roads from this farm */
};
struct road_f *farmroads[MAXFARMS+1]; /* list of roads from each farm */
int farmtime[MAXFARMS+1]; /* best time fo far from farm X to farm[i] */
int onqueue[MAXFARMS+1]; /* this farm is currently being searched */
int queue[MAXFARMS]; /* farms to be 'searched' */
int qnextin, qnextout;
struct road_f *
makeroadfrom (farmsrc, farmdst, traversetime) {
struct road_f *p;
/* perhaps the road already exists! */
for (p = farmroads[farmsrc]; p; p=p->r_next) {
if (p->r_dstfarm == farmdst) {
if (traversetime < p->r_time)
p->r_time = traversetime;
return;
}
}
/* Must create the new road entry and add it: */
p = (struct road_f *) malloc (sizeof (struct road_f));
p->r_dstfarm = farmdst;
p->r_time = traversetime;
/* add to road list */
p->r_next = farmroads[farmsrc];
farmroads[farmsrc] = p;
return p;
}
putq(f) {
if (onqueue[f]) return;
queue[qnextin] = f;
onqueue[f] = 1;
if (++qnextin >= MAXFARMS) qnextin = 0;
if (qnextin == qnextout) exit (9);
}
getq() {
if (qnextin == qnextout) exit (8);
int ret = queue[qnextout];
onqueue[ret] = 0;
if (++qnextout >= MAXFARMS) qnextout = 0;
return ret;
}
main () {
FILE *fin = fopen ("bparty.in", "r");
FILE *fout = fopen ("bparty.out", "w");
struct road_f *p;
int n, m, x, i, from, to, xtime, worsttime;
fscanf(fin, "%d %d %d", &n, &m, &x);
for (i = 0; i < m; i++) {
fscanf (fin, "%d %d %d", &from, &to, &xtime);
p = makeroadfrom (from, to, xtime);
p = makeroadfrom (to, from, xtime);
}
for (i = 1; i <= n; i++)
farmtime[i] = 2000000000;
farmtime[x] = 0;
putq(x);
while (qnextin != qnextout) {
from = getq();
for (p = farmroads[from]; p; p=p->r_next) {
if (farmtime[from] + p->r_time < farmtime[p->r_dstfarm]) {
putq (p->r_dstfarm);
farmtime[p->r_dstfarm] = farmtime[from] + p->r_time;
}
}
}
worsttime = farmtime[1];
for (i = 2; i <= n; i++) {
if (farmtime[i] > worsttime)
worsttime = farmtime[i];
}
fprintf (fout, "%d\n", 2*worsttime);
exit (0);
}