Posted: Wed Jun 07, 2006 7:15 am
Hi ! I did this problem in 2 ways but none of these works
I always get WA!!
here are my codes:
Here is another way to do it:
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
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;
}
(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
