186 - Trip Routing

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

zbogi
New poster
Posts: 15
Joined: Thu Aug 29, 2002 11:00 pm
Location: Bulgaria

186 - Trip Routing

Post by 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?
Tsvetan Bogdanov.
from Brain Explorer - Sofia University - FMI 2
e-mail: zbogi@yahoo.com

zbogi
New poster
Posts: 15
Joined: Thu Aug 29, 2002 11:00 pm
Location: Bulgaria

here is the source code of 186

Post by 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]
Tsvetan Bogdanov.
from Brain Explorer - Sofia University - FMI 2
e-mail: zbogi@yahoo.com

zbogi
New poster
Posts: 15
Joined: Thu Aug 29, 2002 11:00 pm
Location: Bulgaria

I finally solved my problems

Post by zbogi »

So if someone wants help on these two I am ready to help. :lol:
Tsvetan Bogdanov.
from Brain Explorer - Sofia University - FMI 2
e-mail: zbogi@yahoo.com

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am

Post by 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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by 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.
Ami ekhono shopno dekhi...
HomePage

Hackson
New poster
Posts: 35
Joined: Sun Nov 10, 2002 5:36 am

186 PE :(

Post by Hackson »

I have solved this question but PE :cry:
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.... :evil:
Solving problem is a no easy task...

sds1100
Learning poster
Posts: 95
Joined: Sat Dec 10, 2005 2:09 pm

1

Post by sds1100 »

i don't know

mingyun20
New poster
Posts: 2
Joined: Sun Oct 22, 2006 12:36 pm

186 WA Please!

Post by 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
New poster
Posts: 2
Joined: Sun Oct 22, 2006 12:36 pm

kkk

Post by mingyun20 »

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

rhsumon
New poster
Posts: 48
Joined: Wed Aug 23, 2006 12:29 pm
Location: Dhaka

186 PE

Post by 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
New poster
Posts: 6
Joined: Tue Dec 24, 2002 7:43 am
Location: Dhaka, Bangladesh
Contact:

Presentation error in 186

Post by Jatno »

Can anyone please tell me why i get Presentation error????????????? :roll: :oops:


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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

Search your problem first. Don't open a new thread if there is one already.
Ami ekhono shopno dekhi...
HomePage

MauriWilde
New poster
Posts: 14
Joined: Sun Jan 20, 2013 1:58 am

186 - Trip Routing WA

Post by MauriWilde »

Why is this giving me WA?? Please help :(

Code: Select all

AC. Removed.
Thank you in advance. :)
Last edited by MauriWilde on Sun Jun 01, 2014 9:30 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 186 - Trip Routing WA

Post by brianfry713 »

Your implementation of the Floyd-Warshall algorithm assumes 10 cities.
Check input and AC output for thousands of problems on uDebug!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re:

Post by brianfry713 »

Jan wrote: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.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 1 (100-199)”