USACO NOV06 Problem 'block' Analysis

by Richard Peng

Define d(p,k) to be the length of the kth shortest path to vertex p. Then note that for this algorithm, the only relavent distances we have to consider are d(p,1) and d(p,2).

The sketch for the proof of correctness would be if d(i,3) was used for one of the paths, then the two paths with the path leading up to d(i,3) replaced by the paths leading up to d(i,1) and d(i,2) respectively would have lesser costs, contradicting with the claim the resulting path is one of the two shortest paths.

Notice that the state with the minimum distance to the source cannot have its distance reduced as all paths have positive lengths. Therefore, we could 'expand' this vertex by adding new states of the results of travelling to its neighbors from this vertex. By the above claim, it's not necessary to expand from the same vertex more than twice.

Therefore, we could store all the the distances in a priority queue, as long as there are elements in the queue, take out the minmum, if its vertex has not been 'expanded' twice, expand it and add all the new distances to the priority queue.

Since at most 2V expansions can be done, at most 2E nodes can be in the queue at a time, resulting in a runtime of O(ElogE) where E is the number of edges.


#include <algorithm>
#include <queue>
#include <stdio.h>
using namespace std;

int ans[6000][2],t[6000];
int li[100000][3],deg[6000],*e[6000],*c[6000],n,m;

struct dat{
	int p,dis;
	bool operator <(const dat &b) const { return dis > b.dis;}
};

priority_queue<dat> q;
main(){
	FILE *f_in,*f_out;
	int i,j,p,d;
	f_in=fopen("block.in","r");
	f_out=fopen("block.out","w");
	for(fscanf(f_in,"%d%d",&n,&m),memset(deg,0,sizeof(deg)),i=0;i<m;
		fscanf(f_in,"%d%d%d",&li[i][0],&li[i][1],&li[i][2]),
		li[i][0]--,li[i][1]--,deg[li[i][0]]++,deg[li[i][1]]++,i++);
	for(i=0;i<n;e[i]=new(int[deg[i]]),c[i]=new(int[deg[i]]),deg[i]=0,i++);
	for(i=0;i<m;
		e[li[i][0]][deg[li[i][0]]]=li[i][1],
		c[li[i][0]][deg[li[i][0]]]=li[i][2],deg[li[i][0]]++,
		e[li[i][1]][deg[li[i][1]]]=li[i][0],
		c[li[i][1]][deg[li[i][1]]]=li[i][2],deg[li[i][1]]++,i++);

	for(memset(t,0,sizeof(t)),q.push((dat){0,0});!q.empty();q.pop()){
		p=q.top().p;	d=q.top().dis;
		if(t[p]<2){
			ans[p][t[p]]=d;	t[p]++;
			for(i=0;i<deg[p];i++)	if(t[e[p][i]]<2){
				q.push((dat){e[p][i],d+c[p][i]});
			}
		}
	}
	fprintf(f_out,"%d\n",ans[n-1][1]);
	fclose(f_in);
	fclose(f_out);
}