186 - Trip Routing

[zbogi]

Can somebody tell me why 186 and 187 give WA time after time?
Is there some tricky input/output or it is just some spacing or something else?

[zbogi]

I solved the problem with 187, but 186 continues to be WA.
[cpp]#include <stdio.h>
#include <string.h>

int n;
char a[25],b[25],c[15];
int v;
char town[110][25];
char nm[110][110][15];
int vals[110][110];
int m[110][110];

void gstr(char * st,char ch,int len)
{
int i=0;
char c;
while ((c=getchar())!=ch)
st[i++]=c;
for (;i<len;i++)
st=' ';
st='\0';
}

int strton(char * st)
{
int i;
for (i=0;i<n;i++)
if (strcmp(st,town)==0)
break;
if (i==n)
{
strcpy(town[n],st);
n++;
}
return i;
}

void rec(int x,int y)
{
if (m[x][y])
{
rec(x,m[x][y]);
rec(m[x][y],y);
}
else
{
fputs(town[x],stdout);
printf(" ");
fputs(town[y],stdout);
printf(" ");
fputs(nm[x][y],stdout);
printf(" %5d\n",vals[x][y]);
}
}

int main()
{
char ch;
int x,y;
int i,j,k;
while ((ch=getchar())!='\n')
{
ungetc(ch,stdin);
gstr(a,',',20);
gstr(b,',',20);
gstr(c,',',10);
scanf("%d",&v);
x=strton(a);
y=strton(b);
if (vals[x][y]>v || vals[x][y]==0)
{
vals[x][y]=vals[y][x]=v;
strcpy(nm[x][y],c);
strcpy(nm[y][x],c);
}
gets(a);
}
for (i=0;i<n;i++)
strcpy(nm," ");
for (i=0;i<n;i++)
for (j=0;j<n;j++)
if (i!=j)
for (k=0;k<n;k++)
if (vals[k] && vals[k][j] && (vals[j]==0 || vals[j]>vals[k]+vals[k][j]))
{
vals[j]=vals[i][j]=vals[i][k]+vals[k][j];
m[j][i]=m[i][j]=k;
}
while ((ch=getchar())!=-1)
{
ungetc(ch,stdin);
gstr(a,',',20);
gstr(b,'\n',20);
x=strton(a);
y=strton(b);
printf("\n\nFrom To Route Miles\n");
printf("-------------------- -------------------- ---------- -----\n");
rec(x,y);
printf(" -----\n");
printf(" Total %5d\n",vals[x][y]);
}
return 0;
}[/cpp][/cpp]

[zbogi]

So if someone wants help on these two I am ready to help.

[WR]

What's the difference between problems 186, 423, 567 and 627?

I solved the last three but continuously get a WA for 186.

Any ideas?

[Jan]

Three important things...

Code: Select all

1. Edges are bidirectional.
2. There can be more than one path from one place to other.
3. There can be paths with same distance, so for this case u have to take the smaller number of routes

For the second case careful about storing the route name.
And for this case u should choose the minimum distance.

[Hackson]

I have solved this question but PE
I don't know if my interpretation of the output formatting is correct.
Should I output 2 blank lines before each report, which includes the first one also?

I think the output-related problems are very confusing....

[sds1100]

i don't know

[mingyun20]

My Source was correctly produced Example testcases.
But when i submitted my source, i always got WA.
plz anyone help me!!

Here's my source code

Code: Select all

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
using namespace std;

char index[101][21];
char index2[201][11];
int in, in2;
int adj[101][101]; // City
int adj2[101][101]; // Road
bool check[27];
int dist[27];
int trace[27]; 
int tot;
const int INF = 0x5FFFFFFF;
int hash(bool type, char* str)
{
	if(type){ // City
		int i;
		for(i=1; i<=in; i++){
			if(strcmp(index[i], str)==0) return i;
		}
		strcpy(index[++in], str);
		return in;
	}
	else{
		int i;
		for(i=1; i<=in2; i++){
			if(strcmp(index2[i], str)==0) return i;
		}
		strcpy(index2[++in2], str);
		return in2;
	}
}
void Ptrace(int S)
{
	if(S==trace[S]) return;
	Ptrace(trace[S]);
	tot+=adj[trace[S]][S];
	printf("%-20s %-20s %-10s %5d\n",index[trace[S]],index[S],index2[adj2[trace[S]][S]],adj[trace[S]][S]);
}
int main()
{
	char temp[101];
	int i, j;
	for(i=1; i<=100; i++){
		for(j=1; j<=100; j++){
			adj[i][j]=INF;
		}
	}
	while(cin.getline(temp, 101)){
		if(strlen(temp)==0) break;
		int a, b, c, d;
		a=hash(1, strtok(temp, ","));
		b=hash(1, strtok(NULL, ","));
		c=hash(0, strtok(NULL, ","));
		d=atoi(strtok(NULL, "\n"));
		adj[a][b]=adj[b][a]=d;
		adj2[a][b]=adj2[b][a]=c;
	}
	while(cin.getline(temp, 101)){
		int start=hash(1, strtok(temp, ","));
		int end=hash(1, strtok(NULL, "\n"));
		
		for(i=1; i<=26; i++){
			check[i]=0;
			dist[i]=INF;
			trace[i]=0;
		}
		check[start]=1;
		for(i=1; i<=26; i++){
			dist[i]=adj[start][i];
			trace[i]=start;
		}
		while(true){
			int min=INF;
			int minv;
			for(i=1; i<=26; i++){
				if(dist[i]<min&&!check[i]){
					min=dist[i];
					minv=i;
				}
			}
			check[minv]=1;
			for(i=1; i<=26; i++){
				if(dist[i]>dist[minv]+adj[minv][i]&&!check[i]){
					dist[i]=dist[minv]+adj[minv][i];
					trace[i]=minv;
				}
			}
			if(minv==end){
				tot=0;
				cout << "From                 To                   Route      Miles" << endl;
				cout << "-------------------- -------------------- ---------- -----" << endl;
				Ptrace(minv);
				cout << "                                                     -----" << endl;
				printf("                                          Total      %5d\n\n\n ", tot);
				break;
			}
		}
	}
	return 0;
}

[mingyun20]

I Solved.
Becafully read output(San Luis Obispo,Los Angeles)

[rhsumon]

Why PE please anyone check this and ryply:

printf("From To Route Miles\n");
printf("-------------------- -------------------- ---------- -----\n");
for( i=0; i<x-1; i++){
s = find(ans,ans[i+1]);
printf("%-21s%-21s%-12s%4d\n",ans,ans[i+1],road[s].r_name,road[s].dis);
sum += road[s].dis;
}
printf(" -----\n");
printf(" Total%11d\n",sum);

[Jatno]

Can anyone please tell me why i get Presentation error?????????????


Output section of my code:

printf("\n\nFrom To Route Miles\n");
printf("-------------------- -------------------- ---------- -----\n");
for(i=0;i<Track-1;i++) {
................
................
printf("%-20s %-20s ",T[p],T[q]);
printf("%-10s %5ld\n",F[Matrix[p][q]],D[p][q]);
}
printf(" -----\n");
printf(" Total %5ld\n",Total);

[Jan]

Search your problem first. Don't open a new thread if there is one already.

[MauriWilde]

Why is this giving me WA?? Please help

Code: Select all

AC. Removed.

Thank you in advance.

[brianfry713]

Your implementation of the Floyd-Warshall algorithm assumes 10 cities.

[brianfry713]

Three important things...

Code: Select all

1. Edges are bidirectional.
2. There can be more than one path from one place to other.
3. There can be paths with same distance, so for this case u have to take the smaller number of routes

For the second case careful about storing the route name.
And for this case u should choose the minimum distance.

Point 3 is incorrect. In the judge's input there is exactly one shortest route between any pair of cities. Also the graph is connected and the shortest path is always less than 65536.