## 186 - Trip Routing

Moderator: Board moderators

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

### 186 - Trip Routing

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

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

So if someone wants help on these two I am ready to help.
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
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
Contact:
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 :(

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....
Solving problem is a no easy task...

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

### 1

i don't know

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

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;
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]);
}
int main()
{
char temp[101];
int i, j;
for(i=1; i<=100; i++){
for(j=1; j<=100; j++){
}
}
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"));
}
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++){
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++){
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

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

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(" -----\n");
printf(" Total%11d\n",sum);

Jatno
New poster
Posts: 6
Joined: Tue Dec 24, 2002 7:43 am
Contact:

### Presentation error in 186

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Ami ekhono shopno dekhi...
HomePage

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

### 186 - Trip Routing WA

Code: Select all

``````AC. Removed.
``````
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

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:

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!