USACO OPEN07 bparty Analysis

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