## 11047 - The Scrooge Co Problem

Moderator: Board moderators

midra
Experienced poster
Posts: 119
Joined: Fri Feb 13, 2004 7:20 am
Contact:
Hi ! I did this problem in 2 ways but none of these works
I always get WA!!
here are my codes:

Code: Select all

``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MIN(a,b) a<b?a:b

char loc[101][22];
int d[101][101],dist[102],antecesor[102];
bool visited[101];
char init[22],end[22],name[32];

int VecinoMasCerca(int src,int P){
int i,min=40000,pos;
for(i=1;i<=P;i++){
if(!visited[i])
if(dist[i]<min){
min=dist[i];
pos=i;
}
}
return pos;
}

void dijkstra(int src,int dst, int P){
int i,j,pos;
for(i=1;i<=P;i++){
visited[i]=false;
dist[i]=d[src][i];
}
for(i=1;i<=P;i++){
pos=VecinoMasCerca(src,P);
visited[pos]=true;
for(j=1;j<=P;j++)
if(!visited[j])
if(dist[pos]+d[pos][j]<dist[j]){
antecesor[j]=pos;
dist[j]=dist[pos] + d[pos][j];
}
}
}

int main(){
int i,j,k,X,R,P,src,dst;
int path[102];
scanf("%d",&X);
for(i=0;i<X;i++){

scanf("%d",&P);
for(j=1;j<=P;j++)
scanf("%s",&loc[j]);
for(j=1;j<=P;j++)
for(k=1;k<=P;k++){
scanf("%d",&d[j][k]);
if(d[j][k]==-1)
d[j][k]=31000;
}
scanf("%d",&R);
for(j=0;j<R;j++){
scanf("%s %s %s",&name,&init,&end);
for(k=1;k<=P;k++){
antecesor[k]=0;
if(strcmp(init,loc[k])==0)
src=k;
if(strcmp(end,loc[k])==0)
dst=k;
}
dijkstra(src,dst,P);
if(dist[dst]<31000){
printf("Mr %s to go from %s to %s, you will receive %d euros\n",name,loc[src],loc[dst],dist[dst]);
printf("Path:%s",init);
int ind=0;
while(antecesor[dst]!=0){
path[ind++]=antecesor[dst];
dst=antecesor[dst];
}
ind--;
while(ind>=0){
printf(" %s",loc[path[ind]]);
ind--;
}
printf(" %s\n",end);
}
else
printf("Sorry Mr %s you can not go from %s to %s\n",name,init,end);
}
}
return 0;
}
``````

Here is another way to do it:

Code: Select all

``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MIN(a,b) a<b?a:b

char loc[101][22];
int d[101][101],dist[102],prev[102][102];
bool visited[101];
char init[22],end[22],name[32];

void floyd(int P){
int i,j,k;
for(k=1;k<=P;k++)
for(i=1;i<=P;i++)
for(j=1;j<=P;j++)
if(d[i][j]>d[i][k]+d[k][j]){
d[i][j]=d[i][k]+d[k][j];
prev[i][j]=k;
}
}

void printPath(int src,int dst){
if(prev[src][dst]==src) return;
else
printPath(src,prev[src][dst]);
printf(" %s",loc[prev[src][dst]]);
}

int main(){
int i,j,k,X,R,P,src,dst;
int path[102];
scanf("%d",&X);
for(i=0;i<X;i++){
scanf("%d",&P);
for(j=1;j<=P;j++)
scanf("%s",&loc[j]);
for(j=1;j<=P;j++)
for(k=1;k<=P;k++){
scanf("%d",&d[j][k]);
if(d[j][k]==-1)
d[j][k]=31000;
}
for(j=1;j<=P;j++)
for(k=1;k<=P;k++)
prev[j][k]=j;
floyd(P);
scanf("%d",&R);
for(j=0;j<R;j++){
scanf("%s %s %s",&name,&init,&end);
for(k=1;k<=P;k++){
if(strcmp(init,loc[k])==0)
src=k;
if(strcmp(end,loc[k])==0)
dst=k;
}
if(d[src][dst]<31000){
printf("Mr %s to go from %s to %s, you will receive %d euros\n",name,loc[src],loc[dst],d[src][dst]);
printf("Path:%s",init);
printPath(src,dst);
printf(" %s\n",end);
}
else
printf("Sorry Mr %s you can not go from %s to %s\n",name,init,end);
}
}
return 0;
}
``````
I don't understand what's wrong!!! I think both codes have to work for this problem, they work for the samples
(by the way, I know that maybe I have variables that I don't use or something like that, I was just so tired to do the most efficient code, I just want a code that works fine)
maybe I did it in a wrong way dijstra or floyd algorithm, but I don't think so...
if someone can help me I would appreciate very much
thanks
bye

mrahman
New poster
Posts: 25
Joined: Mon Oct 24, 2005 9:45 am
Contact:
Hi Midra,
Just Change in your floyd function

Code: Select all

``````void floyd(int P){
int i,j,k;
for(k=1;k<=P;k++)
for(i=1;i<=P;i++)
for(j=1;j<=P;j++)
if(d[i][j]>d[i][k]+d[k][j]){
d[i][j]=d[i][k]+d[k][j];
prev[i][j]=k;  [b]// change this to prev[i][j] = prev[k][j];[/b]
}
}``````
Hope this will help
Practice Makes a man perfect

arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:
mrahman wrote:Hi Midra,
Just Change in your floyd function

Code: Select all

``````void floyd(int P){
int i,j,k;
for(k=1;k<=P;k++)
for(i=1;i<=P;i++)
for(j=1;j<=P;j++)
if(d[i][j]>d[i][k]+d[k][j]){
d[i][j]=d[i][k]+d[k][j];
prev[i][j]=k;  [b]// change this to prev[i][j] = prev[k][j];[/b]
}
}``````
Hope this will help
however i've got AC with prev[j] = k , so i think it is right , but midra did wrong in his printPath method
In being unlucky I have the record.

mrahman
New poster
Posts: 25
Joined: Mon Oct 24, 2005 9:45 am
Contact:
arsalan_mousavian, I know there are both ways to makeup Midra's mistake. One is to change printPath method and other I mentioned in my previous post. I wrote the simpliest one in my previos post. Anyway thank you for your acknowledgement.

Sorry for my poor english
Practice Makes a man perfect

C
New poster
Posts: 35
Joined: Mon Apr 17, 2006 1:04 pm
I used dijkstra algo, and it passes all available input, but I still got WA. I really don't know what may be wrong, hope someone can help,please! I post my code here, after I find the mistake I will cut it.

Code: Select all

``````#include <stdio.h>
#include <string.h>

int main(void)
{
int t,n,m;
int i,j,k;
char city[99][21];
int dis[99][99];
int p[99];
char b[99];
int d[99];
int cur;
char name[31],s[21],q[21];
int si,qi,min;

scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%s",city+i);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",dis[i]+j);
scanf("%d",&m);
for(i=0;i<m;i++)
{
scanf("%s %s %s",name,s,q);
si=0;
while(strcmp(s,city[si]))si++;
qi=0;
while(strcmp(q,city[qi]))qi++;
for(j=0;j<n;j++)
{
p[j]=si;
b[j]=1;
if(dis[si][j]!=-1)d[j]=dis[si][j];else d[j]= (1<<30);
}
b[si]=0;
for(j=0;j<n-1;j++)
{
min=(1<<30)+1;
for(k=0;k<n;k++)
if(b[k]&&(d[k]<min)){min=d[k]; cur=k;}
for(k=0;k<n;k++)
{
if((dis[cur][k]!=-1)&&(d[cur]+dis[cur][k]<d[k]))
{
p[k]= cur;
d[k]= d[cur]+dis[cur][k];
}
}
b[cur]=0;
}
if(d[qi]<(1<<30))
{
printf("Mr %s to go from %s to %s, you will receive %d euros\n",name,city[si],city[qi],d[qi]);
j=-1;  k=p[qi];
while(k!=si)
{
d[++j]= k;
k= p[k];
}
printf("Path:%s ",city[si]);
for(k=j;k>=0;k--)
printf("%s ",city[d[k]]);
printf("%s\n",city[qi]);
}
else printf("Sorry Mr %s you can not go from %s to %s\n",name,city[si],city[qi]);
}
}

return 0;
}
``````

StatujaLeha
Learning poster
Posts: 91
Joined: Tue May 31, 2005 2:01 pm
Location: Russia
Please, give me output for this input
3
4
g1 g2 g3 g4
10 1 0 -1
1 1 2 -1
-1 -1 2 3
-1 -1 -1 5
16
leha1 g1 g1
leha2 g1 g2
leha3 g1 g3
leha4 g1 g4
leha5 g2 g1
leha6 g2 g2
leha7 g2 g3
leha8 g2 g4
leha9 g3 g1
leha10 g3 g2
leha11 g3 g3
leha12 g3 g4
leha13 g4 g1
leha14 g4 g2
leha15 g4 g3
leha16 g4 g4
4
g1 g2 g3 g4
10 1 0 -1
-1 1 2 -1
-1 -1 2 3
1 -1 -1 4
16
leha1 g1 g1
leha2 g1 g2
leha3 g1 g3
leha4 g1 g4
leha5 g2 g1
leha6 g2 g2
leha7 g2 g3
leha8 g2 g4
leha9 g3 g1
leha10 g3 g2
leha11 g3 g3
leha12 g3 g4
leha13 g4 g1
leha14 g4 g2
leha15 g4 g3
leha16 g4 g4
4
g1 g2 g3 g4
10 1 0 3
-1 1 2 -1
-1 -1 2 3
1 -1 -1 2
16
leha1 g1 g1
leha2 g1 g2
leha3 g1 g3
leha4 g1 g4
leha5 g2 g1
leha6 g2 g2
leha7 g2 g3
leha8 g2 g4
leha9 g3 g1
leha10 g3 g2
leha11 g3 g3
leha12 g3 g4
leha13 g4 g1
leha14 g4 g2
leha15 g4 g3
leha16 g4 g4

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm
My AC code gives the following Output:

Code: Select all

``````Mr leha1 to go from g1 to g1, you will receive 2 euros
Path:g1 g2 g1
Mr leha2 to go from g1 to g2, you will receive 1 euros
Path:g1 g2
Mr leha3 to go from g1 to g3, you will receive 0 euros
Path:g1 g3
Mr leha4 to go from g1 to g4, you will receive 3 euros
Path:g1 g3 g4
Mr leha5 to go from g2 to g1, you will receive 1 euros
Path:g2 g1
Mr leha6 to go from g2 to g2, you will receive 1 euros
Path:g2 g2
Mr leha7 to go from g2 to g3, you will receive 1 euros
Path:g2 g1 g3
Mr leha8 to go from g2 to g4, you will receive 4 euros
Path:g2 g1 g3 g4
Sorry Mr leha9 you can not go from g3 to g1
Sorry Mr leha10 you can not go from g3 to g2
Mr leha11 to go from g3 to g3, you will receive 2 euros
Path:g3 g3
Mr leha12 to go from g3 to g4, you will receive 3 euros
Path:g3 g4
Sorry Mr leha13 you can not go from g4 to g1
Sorry Mr leha14 you can not go from g4 to g2
Sorry Mr leha15 you can not go from g4 to g3
Mr leha16 to go from g4 to g4, you will receive 5 euros
Path:g4 g4

Mr leha1 to go from g1 to g1, you will receive 4 euros
Path:g1 g3 g4 g1
Mr leha2 to go from g1 to g2, you will receive 1 euros
Path:g1 g2
Mr leha3 to go from g1 to g3, you will receive 0 euros
Path:g1 g3
Mr leha4 to go from g1 to g4, you will receive 3 euros
Path:g1 g3 g4
Mr leha5 to go from g2 to g1, you will receive 6 euros
Path:g2 g3 g4 g1
Mr leha6 to go from g2 to g2, you will receive 1 euros
Path:g2 g2
Mr leha7 to go from g2 to g3, you will receive 2 euros
Path:g2 g3
Mr leha8 to go from g2 to g4, you will receive 5 euros
Path:g2 g3 g4
Mr leha9 to go from g3 to g1, you will receive 4 euros
Path:g3 g4 g1
Mr leha10 to go from g3 to g2, you will receive 5 euros
Path:g3 g4 g1 g2
Mr leha11 to go from g3 to g3, you will receive 2 euros
Path:g3 g3
Mr leha12 to go from g3 to g4, you will receive 3 euros
Path:g3 g4
Mr leha13 to go from g4 to g1, you will receive 1 euros
Path:g4 g1
Mr leha14 to go from g4 to g2, you will receive 2 euros
Path:g4 g1 g2
Mr leha15 to go from g4 to g3, you will receive 1 euros
Path:g4 g1 g3
Mr leha16 to go from g4 to g4, you will receive 4 euros
Path:g4 g4

Mr leha1 to go from g1 to g1, you will receive 4 euros
Path:g1 g4 g1
Mr leha2 to go from g1 to g2, you will receive 1 euros
Path:g1 g2
Mr leha3 to go from g1 to g3, you will receive 0 euros
Path:g1 g3
Mr leha4 to go from g1 to g4, you will receive 3 euros
Path:g1 g4
Mr leha5 to go from g2 to g1, you will receive 6 euros
Path:g2 g3 g4 g1
Mr leha6 to go from g2 to g2, you will receive 1 euros
Path:g2 g2
Mr leha7 to go from g2 to g3, you will receive 2 euros
Path:g2 g3
Mr leha8 to go from g2 to g4, you will receive 5 euros
Path:g2 g3 g4
Mr leha9 to go from g3 to g1, you will receive 4 euros
Path:g3 g4 g1
Mr leha10 to go from g3 to g2, you will receive 5 euros
Path:g3 g4 g1 g2
Mr leha11 to go from g3 to g3, you will receive 2 euros
Path:g3 g3
Mr leha12 to go from g3 to g4, you will receive 3 euros
Path:g3 g4
Mr leha13 to go from g4 to g1, you will receive 1 euros
Path:g4 g1
Mr leha14 to go from g4 to g2, you will receive 2 euros
Path:g4 g1 g2
Mr leha15 to go from g4 to g3, you will receive 1 euros
Path:g4 g1 g3
Mr leha16 to go from g4 to g4, you will receive 2 euros
Path:g4 g4
``````
(Edited now.)
Last edited by asif_rahman0 on Fri Aug 25, 2006 5:34 pm, edited 1 time in total.

StatujaLeha
Learning poster
Posts: 91
Joined: Tue May 31, 2005 2:01 pm
Location: Russia
My solution outputs the same except it doesn't print "\n\n" between test cases. In problem's description it isn't said about this. Why do you print "\n\n"?

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm
my wish

gauravc
New poster
Posts: 2
Joined: Thu Apr 02, 2009 12:11 am

### Re: 11047 - The Scrooge Co Problem

arsalan_mousavian wrote:
C wrote:My code also passes all i/os here,but i still got WA. Could anyone give some more i/os?

It is a simple shortest-path problem, right ??
yes , but maybe you do some thing wrong in printing the path , or you assign too high value when cost of 2 vertex is -1 that cause integer overflow

Hope it Helps

Arsalan
Hey Arsalan, I am unable to find the correct algo to print the path. Please can you guide me?

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Contact:

### Re: 11047 - The Scrooge Co Problem

For above case my AC code produces different output:

Code: Select all

``````Mr leha1 to go from g1 to g1, you will receive 2 euros
Path:g1 g1
Mr leha2 to go from g1 to g2, you will receive 1 euros
Path:g1 g2
Mr leha3 to go from g1 to g3, you will receive 0 euros
Path:g1 g3
Mr leha4 to go from g1 to g4, you will receive 3 euros
Path:g1 g3 g4
Mr leha5 to go from g2 to g1, you will receive 1 euros
Path:g2 g1
Mr leha6 to go from g2 to g2, you will receive 1 euros
Path:g2 g2
Mr leha7 to go from g2 to g3, you will receive 1 euros
Path:g2 g1 g3
Mr leha8 to go from g2 to g4, you will receive 4 euros
Path:g2 g1 g3 g4
Sorry Mr leha9 you can not go from g3 to g1
Sorry Mr leha10 you can not go from g3 to g2
Mr leha11 to go from g3 to g3, you will receive 2 euros
Path:g3 g3
Mr leha12 to go from g3 to g4, you will receive 3 euros
Path:g3 g4
Sorry Mr leha13 you can not go from g4 to g1
Sorry Mr leha14 you can not go from g4 to g2
Sorry Mr leha15 you can not go from g4 to g3
Mr leha16 to go from g4 to g4, you will receive 5 euros
Path:g4 g4
Mr leha1 to go from g1 to g1, you will receive 4 euros
Path:g1 g1
Mr leha2 to go from g1 to g2, you will receive 1 euros
Path:g1 g2
Mr leha3 to go from g1 to g3, you will receive 0 euros
Path:g1 g3
Mr leha4 to go from g1 to g4, you will receive 3 euros
Path:g1 g3 g4
Mr leha5 to go from g2 to g1, you will receive 6 euros
Path:g2 g3 g4 g1
Mr leha6 to go from g2 to g2, you will receive 1 euros
Path:g2 g2
Mr leha7 to go from g2 to g3, you will receive 2 euros
Path:g2 g3
Mr leha8 to go from g2 to g4, you will receive 5 euros
Path:g2 g3 g4
Mr leha9 to go from g3 to g1, you will receive 4 euros
Path:g3 g4 g1
Mr leha10 to go from g3 to g2, you will receive 5 euros
Path:g3 g4 g1 g2
Mr leha11 to go from g3 to g3, you will receive 2 euros
Path:g3 g3
Mr leha12 to go from g3 to g4, you will receive 3 euros
Path:g3 g4
Mr leha13 to go from g4 to g1, you will receive 1 euros
Path:g4 g1
Mr leha14 to go from g4 to g2, you will receive 2 euros
Path:g4 g1 g2
Mr leha15 to go from g4 to g3, you will receive 1 euros
Path:g4 g1 g3
Mr leha16 to go from g4 to g4, you will receive 4 euros
Path:g4 g4
Mr leha1 to go from g1 to g1, you will receive 4 euros
Path:g1 g1
Mr leha2 to go from g1 to g2, you will receive 1 euros
Path:g1 g2
Mr leha3 to go from g1 to g3, you will receive 0 euros
Path:g1 g3
Mr leha4 to go from g1 to g4, you will receive 3 euros
Path:g1 g4
Mr leha5 to go from g2 to g1, you will receive 6 euros
Path:g2 g3 g4 g1
Mr leha6 to go from g2 to g2, you will receive 1 euros
Path:g2 g2
Mr leha7 to go from g2 to g3, you will receive 2 euros
Path:g2 g3
Mr leha8 to go from g2 to g4, you will receive 5 euros
Path:g2 g3 g4
Mr leha9 to go from g3 to g1, you will receive 4 euros
Path:g3 g4 g1
Mr leha10 to go from g3 to g2, you will receive 5 euros
Path:g3 g4 g1 g2
Mr leha11 to go from g3 to g3, you will receive 2 euros
Path:g3 g3
Mr leha12 to go from g3 to g4, you will receive 3 euros
Path:g3 g4
Mr leha13 to go from g4 to g1, you will receive 1 euros
Path:g4 g1
Mr leha14 to go from g4 to g2, you will receive 2 euros
Path:g4 g1 g2
Mr leha15 to go from g4 to g3, you will receive 1 euros
Path:g4 g1 g3
Mr leha16 to go from g4 to g4, you will receive 2 euros
Path:g4 g4
``````
Hope this helps

skyhigh_
New poster
Posts: 4
Joined: Fri May 25, 2012 7:43 am

### 11047 WHY WA ????

Code: Select all

``````#include<algorithm>
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
#include<deque>
#define pi 2*acos(0.0)

#define inf 9999999
using namespace std;

// variable list

int t,c,i,j,k,n,q,dist,x,y;
int d[103][103]; // d[i][j] = distance from i to j
int pred[103][103]; // pred[i][j] = intermediate vertix from i to j
char name[33];
char place[33],src[33],des[33];

map < string, int > index;
map < int, string > nam;

// for printing path
void Path(int src,int dst)
{
if(pred[src][dst]==src) return;
else  Path(src,pred[src][dst]);

cout << " " << nam[pred[src][dst]];
}

int main()
{
scanf("%d",&t);
while( t-- )
{
scanf("%d%*c",&n);

index.clear();
nam.clear();

for(i=1; i<=n; i++)
{
cin >> place;

index[place] = i;
nam[i] = place;
}

for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
{
scanf("%d",&dist);
if(dist==-1) dist =inf;
d[i][j] = dist;
}
}

for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
pred[i][j] = i;

//for(i=1; i<=n; i++) d[i][i] = 0;

// floyd warshall

for(k=1; k<=n; k++)
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
{
if(d[i][j]>d[i][k]+d[k][j])
{
d[i][j] = d[i][k]+d[k][j];
pred[i][j] =k;
}
}

scanf("%d%*c",&q);

for(k=1; k<=q; k++)
{
cin >> name >> src >> des;

i = index[src];
j = index[des];

if(d[i][j]==inf) printf("Sorry Mr %s you can not go from %s to %s\n",name,src,des);

else
{
printf("Mr %s to go from %s to %s, you will receive %d euros\n",name,src,des,d[i][j]);
printf("Path:");

cout << src ;
Path(i,j);
cout << " " << des << endl;
}
}
}
return 0;
}

``````

skyhigh_
New poster
Posts: 4
Joined: Fri May 25, 2012 7:43 am

### Re: 11047 WHY WA ????

need help !!!!!!!!

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

### Re: 11047 WHY WA ????

Doesn't match the sample I/O and gives a seg fault on my machine.
Check input and AC output for thousands of problems on uDebug!

skyhigh_
New poster
Posts: 4
Joined: Fri May 25, 2012 7:43 am

### Re: 11047 WHY WA ????

i got ac !!
there was a problem in path printing