OJ Board

Code: Select all

 path[i][j] = k 

Code: Select all

 path[i][j] = path[k][j] 

Code: Select all

[c]

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int cost[101][101],tax[101],path[101][101];
int n,s,d,max=10000;
void init();
void getpath(int r,int c)
{
	int k;
	k=path[r][c];
	if(k!=-1)
	{
		getpath(r,k);
		getpath(k,c);
		printf("%d-->",k);
	}
}
void main(void)
{
		char ch,str[15],temp[10];
		int i,j,k,total,l,len;
		scanf("%d",&total);
		for(l=0;l<total;l++)
		{
			n=0;
			while(3)
			{
				scanf("%d%c",&cost[1][++n],&ch);
					if(ch=='\n')
						break;
			}
			for(i=2;i<=n;i++)
				for(j=1;j<=n;j++)
					scanf("%d",&cost[i][j]);
			for(i=1;i<=n;i++)
				scanf("%d",&tax[i]);
			for(i=1; i<=n; i++)
				for(j=1; j<=n; j++)
				{
					if(cost[i][j] == -1)
						 cost[i][j] = 10000;
					path[i][j]=-1;
				}
			for(k=1;k<=n;k++)
				for(i=1;i<=n;i++)
					for(j=1;j<=n;j++)
						if((cost[i][k]+cost[k][j]+tax[k])<cost[i][j])
						{
							cost[i][j]=cost[i][k]+cost[k][j]+tax[k];
							path[i][j]=k;
						}
			getchar();
			while(1)
			{
				gets(str);
				len=strlen(str);
				if(len==0)	break;
				s=atoi(str);
				for(i=1;i<len;i++)
					if(str[i]==' ') break;
				for(j=i,k=0;j<len;j++)
					temp[k++]=str[j];
				d=atoi(temp);
				printf("From %d to %d :\n",s,d);
				printf("Path: %d-->",s);
				getpath(s,d);
				printf("%d\n",d);
				printf("Total cost : %d\n\n",cost[s][d]);
				for(i=0;i<k;i++)
					temp[k]='\0';
				for(i=0;i<len;i++)
					str[i]='\0';
			}
			init();
		}
}
void init()
{
	int i,j;
	for(i=0;i<=100;i++)
	{
		for(j=0;j<=100;j++)
			cost[i][j]=0;
		tax[i]=0;	
	}
}

[/c]

Code: Select all

[c]
#include<stdio.h>

#define DIM		8192
#define NIL		-1
#define INFINITY	2000000000
#define MIN(x, y)	((x)>(y)?(y):(x))

int FWAlgo();
void printpath(int i, int j);
void init();
void read();
long int D[DIM][DIM];
long int Tax[DIM];
int Pred[DIM][DIM];
int nvertices;
char buf[1024];

int FWAlgo()
{
	int k, i, j, p;

	for( k = 0; k < nvertices; k++ )
	{
		for( i = 0; i < nvertices; i++ )
		{
			for( j = 0; j < nvertices; j++ )
			{
				if( i != j ) 
				{
					p = D[i][k] + D[k][j] + Tax[k];
					if( p>=D[i][j] )							 
					{
						Pred[i][j] = Pred[i][j];
					}
					else 
					{
						Pred[i][j] = Pred[k][j];
					}
					D[i][j] = MIN(D[i][j], p);
				}
			}
		}
	}
}

void printpath(int i, int j)
{
	if( i == j)
	{
		printf("%d", i+1);
	}
	else if( Pred[i][j] == NIL )
	{
		printf("No path from %d to %d exists.\n", i+1, j+1);
	}
	else 
	{
		printpath(i, Pred[i][j]);
		printf("-->%d", j+1);
	}
}

void read()
{
	int i, len, k, j, c;
	long wt;
	char text[32];

	nvertices = 0;
	if( fgets(buf, 1024, stdin) )
	{
		len = strlen(buf);
		for( i = 0; i < len; )
		{
			k = 0;
			if( buf[i] == '-' || isdigit(buf[i]) )
			{
				do {
					text[k++] = buf[i++];
				}while( isdigit(buf[i]) );
				text[k] = '\0';
				wt = atol(text);
				D[0][nvertices++] = wt<0?INFINITY:wt;
			}
			else i++;
		}
	}
	else exit(0);

	for( i = 1; i < nvertices; i++ )
	{
		for( j = 0; j < nvertices; j++ )
		{
			scanf("%ld", &wt);
			D[i][j] = wt<0?INFINITY:wt;
			Pred[i][j] = i;
		}
	}
	for( i = 0; i < nvertices; i++ )
	{
		scanf("%ld", &Tax[i]);
	}
}

void init()
{
	int i, j;

	for( i = 0; i < DIM; i++ )
	{
		for( j = 0; j < DIM; j++ )
		{
			if( i == j )
			{
				D[i][j] = 0;
			}
			else 
			{
				D[i][j] = INFINITY;
			}
			Pred[i][j] = NIL;
		}
	}
}

int main()
{
	int a, b;
	int ncase;

	scanf("%d", &ncase);
	getchar();
	getchar();
	while( ncase-- )
	{
		read();
		FWAlgo();
		while( getchar() != '\n' )
			;
		while( fgets(buf, 1024, stdin) && sscanf(buf, "%d %d", &a, &b) == 2 )
		{
			printf("From %d to %d :\n", a, b);
			printf("Path: ");
			printpath(a-1, b-1);
			printf("\nTotal cost : %ld\n\n", D[a-1][b-1]);
		}
	}
	return 0;
}
[/c]

Code: Select all

void getpath(int r,int c)
{
   int k;
   k=path[r][c];
   if(k!=-1)
   {
      getpath(r,k);
      printf("%d-->",k);
      getpath(k,c);
   }
}