383  Shipping Routes
Moderator: Board moderators

 Experienced poster
 Posts: 187
 Joined: Wed Dec 11, 2002 2:03 pm
 Location: Mount Papandayan, Garut
383  Shipping Route
i use simple floyd warshall to solve this problem, and it should be work, but still i got WA. can anyone help me? can you give me sample input?
here is my code :
[c]
 cut, got AC
[/c]
here is my code :
[c]
 cut, got AC
[/c]
Last edited by titid_gede on Sat May 17, 2003 9:31 am, edited 1 time in total.

 Experienced poster
 Posts: 187
 Joined: Wed Dec 11, 2002 2:03 pm
 Location: Mount Papandayan, Garut

 New poster
 Posts: 44
 Joined: Wed Aug 14, 2002 3:02 am
383 PE
90% got PE... What is the cause... I have try many combination of space and new line by always got PE..How to get acc in this problem??
383  Shipping Routes
Hello there,
I am trying to solve 383, where the aim is to find the minimum path between two vertexes in a three.
I use a class called Node to represent a vertex and another one called Path to represent a path between two nodes.
First, as I read the connections I put the nodes appart by setting their group id....
Then whenever I have to check for the minimum path, I first check the vertexes group id. If they are different, there is no path between them... otherwise I try a breadth first search starting at FROM going to TO.
[cpp]
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
using namespace std;
class Node {
public:
string name;
vector<Node *> children;
int group;
bool operator == (Node &n2) {
return name==n2.name;
}
};
class Path {
public:
vector<Node *> nodes;
Node *lastNode() {
return nodes[nodes.size()1];
}
void add(Node *n) {
nodes.push_back(n);
}
bool contains(Node *n) {
return find(nodes.begin(),nodes.end(),n)!=nodes.end();
}
void copy(Path *c) {
for(int i=0;i!=c>nodes.size();i++) {
add(c>nodes);
}
}
};
int nodeCount;
map<string,Node *> nodes;
vector<Node *> nodesVector;
vector<Node *> hasBeenAtList;
/*
* Checks whether this node has been visited in an earlier path
*/
bool hasBeenAt(Node *n) {
return find(hasBeenAtList.begin(),hasBeenAtList.end(),n)!=hasBeenAtList.end();
}
int getDistanceBetween(Node *from,Node *to) {
vector<Path *> pilha;
Path *c1 = new Path();
c1>add(from);
pilha.push_back(c1);
hasBeenAtList.clear();
while(!pilha.empty()) {
Path *c = pilha[0];
pilha.erase(pilha.begin());
hasBeenAtList.push_back(c>lastNode());
// para cada node conectado ao ultimo
for(int i=0;i!=c>lastNode()>children.size();i++) {
if(c>lastNode()>children==to) {
// achou
return c>nodes.size();
} else {
// se ainda nao estiver no Path
if(!hasBeenAt(c>lastNode()>children)) {
Path *novo = new Path();
novo>copy(c);
novo>add(c>lastNode()>children);
pilha.push_back(novo);
}
}
}
}
return 0;
}
int main(int argc, char **argv) {
int questionCount;
int connectionCount;
int inst;
int inst2 = 0;
int i;
int z;
cin >> inst;
cout << "SHIPPING ROUTES OUTPUT" << endl;
while(inst!=0) {
nodes.clear();
nodesVector.clear();
cout << endl << "DATA SET " << (++inst2) << endl << endl;
cin >> nodeCount >> connectionCount >> questionCount;
for(i=0;i!=nodeCount;i++) {
Node *n = new Node();
cin >> n>name;
n>group = i + 1;
nodes[n>name]=n;
nodesVector.push_back(n);
}
string a,b;
for(i=0;i!=connectionCount;i++) {
cin >> a >> b;
Node *n1 = nodes[a];
Node *n2 = nodes;
n1>children.push_back(n2);
n2>children.push_back(n1);
// para todos os nodes, checa se eh o mesmo
for(z=0;z!=nodesVector.size();z++) {
if(nodesVector[z]>group==n2>group) {
nodesVector[z]>group = n1>group;
}
}
}
int peso;
for(i=0;i!=questionCount;i++) {
cin >> peso >> a >> b;
if(nodes[a]>group==nodes>group) {
cout << "$" << (peso * getDistanceBetween(nodes[a],nodes) * 100) << endl;
} else {
cout << "NO SHIPMENT POSSIBLE" << endl;
}
}
}
return 0;
}
[/cpp]
I believe the problem might be with the io.... it seems weird to have to output such a thing with two spaces (or is it formatted?):
DATA SET 1
Anyone has any idea?
Thanks
Guilherme
I am trying to solve 383, where the aim is to find the minimum path between two vertexes in a three.
I use a class called Node to represent a vertex and another one called Path to represent a path between two nodes.
First, as I read the connections I put the nodes appart by setting their group id....
Then whenever I have to check for the minimum path, I first check the vertexes group id. If they are different, there is no path between them... otherwise I try a breadth first search starting at FROM going to TO.
[cpp]
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
using namespace std;
class Node {
public:
string name;
vector<Node *> children;
int group;
bool operator == (Node &n2) {
return name==n2.name;
}
};
class Path {
public:
vector<Node *> nodes;
Node *lastNode() {
return nodes[nodes.size()1];
}
void add(Node *n) {
nodes.push_back(n);
}
bool contains(Node *n) {
return find(nodes.begin(),nodes.end(),n)!=nodes.end();
}
void copy(Path *c) {
for(int i=0;i!=c>nodes.size();i++) {
add(c>nodes);
}
}
};
int nodeCount;
map<string,Node *> nodes;
vector<Node *> nodesVector;
vector<Node *> hasBeenAtList;
/*
* Checks whether this node has been visited in an earlier path
*/
bool hasBeenAt(Node *n) {
return find(hasBeenAtList.begin(),hasBeenAtList.end(),n)!=hasBeenAtList.end();
}
int getDistanceBetween(Node *from,Node *to) {
vector<Path *> pilha;
Path *c1 = new Path();
c1>add(from);
pilha.push_back(c1);
hasBeenAtList.clear();
while(!pilha.empty()) {
Path *c = pilha[0];
pilha.erase(pilha.begin());
hasBeenAtList.push_back(c>lastNode());
// para cada node conectado ao ultimo
for(int i=0;i!=c>lastNode()>children.size();i++) {
if(c>lastNode()>children==to) {
// achou
return c>nodes.size();
} else {
// se ainda nao estiver no Path
if(!hasBeenAt(c>lastNode()>children)) {
Path *novo = new Path();
novo>copy(c);
novo>add(c>lastNode()>children);
pilha.push_back(novo);
}
}
}
}
return 0;
}
int main(int argc, char **argv) {
int questionCount;
int connectionCount;
int inst;
int inst2 = 0;
int i;
int z;
cin >> inst;
cout << "SHIPPING ROUTES OUTPUT" << endl;
while(inst!=0) {
nodes.clear();
nodesVector.clear();
cout << endl << "DATA SET " << (++inst2) << endl << endl;
cin >> nodeCount >> connectionCount >> questionCount;
for(i=0;i!=nodeCount;i++) {
Node *n = new Node();
cin >> n>name;
n>group = i + 1;
nodes[n>name]=n;
nodesVector.push_back(n);
}
string a,b;
for(i=0;i!=connectionCount;i++) {
cin >> a >> b;
Node *n1 = nodes[a];
Node *n2 = nodes;
n1>children.push_back(n2);
n2>children.push_back(n1);
// para todos os nodes, checa se eh o mesmo
for(z=0;z!=nodesVector.size();z++) {
if(nodesVector[z]>group==n2>group) {
nodesVector[z]>group = n1>group;
}
}
}
int peso;
for(i=0;i!=questionCount;i++) {
cin >> peso >> a >> b;
if(nodes[a]>group==nodes>group) {
cout << "$" << (peso * getDistanceBetween(nodes[a],nodes) * 100) << endl;
} else {
cout << "NO SHIPMENT POSSIBLE" << endl;
}
}
}
return 0;
}
[/cpp]
I believe the problem might be with the io.... it seems weird to have to output such a thing with two spaces (or is it formatted?):
DATA SET 1
Anyone has any idea?
Thanks
Guilherme
383 WA
[pascal]var
dummy:char;
a,b,c,d:longint;
i,j,k:longint;
n,m,p:longint;
u,v:longint;
novertex:longint;
ts:string;
s,s2:string[2];
cost:array[0..800,0..800] of longint;
lst:array[0..300] of string[2];
function min(a,b:longint):longint;
begin
min:=a;
if b<a then
min:=b;
end;
begin
writeln('SHIPPING ROUTES OUTPUT');
writeln;
readln(a);
for c:=1 to a do
begin
novertex:=0;
readln(n,m,p);
for i:=1 to n do
for j:=1 to n do
cost[j]:=2000000;
for i:=1 to n do
cost:=0;
for i:=1 to n do
read(lst,dummy);
readln;
for i:=1 to m do
begin
readln(s,dummy,s2);
for j:=1 to n do
if lst[j]=s then
break;
for k:=1 to n do
if lst[k]=s2 then
break;
cost[j][k]:=1;
cost[k][j]:=1;
end;
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
cost[j]:=min(cost[j],cost[k]+cost[k][j]);
writeln('DATA SET ',c);
writeln;
{write(' ');
for i:=1 to n do
write(lst:8);
writeln;
for i:=1 to n do
begin
write(lst:3);
for j:=1 to n do
write(cost[j]:8);
writeln;
end;}
for i:=1 to p do
begin
readln(ts);
s:=ts[length(ts)1]+ts[length(ts)];
s2:=ts[length(ts)4]+ts[length(ts)3];
val(copy(ts,1,pos(' ',ts)1),a,b);
for j:=1 to n do
if lst[j]=s then
break;
for k:=1 to n do
if lst[k]=s2 then
break;
if (cost[j][k]<>2000000) then
writeln('$',a*cost[j][k]*100)
else
writeln('NO SHIPMENT POSSIBLE');
end;
writeln;
end;
writeln;
writeln('END OF OUTPUT');
end.
[/pascal]
Why i got WA??
Shouldn't i apply warshall in this problem?
dummy:char;
a,b,c,d:longint;
i,j,k:longint;
n,m,p:longint;
u,v:longint;
novertex:longint;
ts:string;
s,s2:string[2];
cost:array[0..800,0..800] of longint;
lst:array[0..300] of string[2];
function min(a,b:longint):longint;
begin
min:=a;
if b<a then
min:=b;
end;
begin
writeln('SHIPPING ROUTES OUTPUT');
writeln;
readln(a);
for c:=1 to a do
begin
novertex:=0;
readln(n,m,p);
for i:=1 to n do
for j:=1 to n do
cost[j]:=2000000;
for i:=1 to n do
cost:=0;
for i:=1 to n do
read(lst,dummy);
readln;
for i:=1 to m do
begin
readln(s,dummy,s2);
for j:=1 to n do
if lst[j]=s then
break;
for k:=1 to n do
if lst[k]=s2 then
break;
cost[j][k]:=1;
cost[k][j]:=1;
end;
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
cost[j]:=min(cost[j],cost[k]+cost[k][j]);
writeln('DATA SET ',c);
writeln;
{write(' ');
for i:=1 to n do
write(lst:8);
writeln;
for i:=1 to n do
begin
write(lst:3);
for j:=1 to n do
write(cost[j]:8);
writeln;
end;}
for i:=1 to p do
begin
readln(ts);
s:=ts[length(ts)1]+ts[length(ts)];
s2:=ts[length(ts)4]+ts[length(ts)3];
val(copy(ts,1,pos(' ',ts)1),a,b);
for j:=1 to n do
if lst[j]=s then
break;
for k:=1 to n do
if lst[k]=s2 then
break;
if (cost[j][k]<>2000000) then
writeln('$',a*cost[j][k]*100)
else
writeln('NO SHIPMENT POSSIBLE');
end;
writeln;
end;
writeln;
writeln('END OF OUTPUT');
end.
[/pascal]
Why i got WA??
Shouldn't i apply warshall in this problem?
hm, i just tried this problem to see and also got PE...
i followed your advice about only one blank line when p==0, but still PE
here are the parts of my code that actually involve newlines:
[c]
printf("SHIPPING ROUTES OUTPUT\n\n");
for (caseno=0;caseno<cases;caseno++) {
printf("DATA SET %d\n\n",caseno+1);
for (i=0;i<p;i++) {
scanf("%d %s %s",&k,temp,temp2);
j = distance from temp to temp2;
if (j==INFTY) printf("NO SHIPMENT POSSIBLE\n");
else printf("$%d\n",j*k*100);
}
if (p) printf("\n");
}
printf("END OF OUTPUT\n");
[/c]
i followed your advice about only one blank line when p==0, but still PE
here are the parts of my code that actually involve newlines:
[c]
printf("SHIPPING ROUTES OUTPUT\n\n");
for (caseno=0;caseno<cases;caseno++) {
printf("DATA SET %d\n\n",caseno+1);
for (i=0;i<p;i++) {
scanf("%d %s %s",&k,temp,temp2);
j = distance from temp to temp2;
if (j==INFTY) printf("NO SHIPMENT POSSIBLE\n");
else printf("$%d\n",j*k*100);
}
if (p) printf("\n");
}
printf("END OF OUTPUT\n");
[/c]

 New poster
 Posts: 12
 Joined: Mon Mar 28, 2005 7:55 pm
 Contact:
383  I BEG(!) you to hepl me!!!!!!
Hi. I have solved a couple of problems just like this one with BFS, but this one gives me WA. The only thing I ask for is to get a single test case this prog fails on!
Here's the code...
Got AC  no code sorry...
Here's the code...
Got AC  no code sorry...
Last edited by Lord Nemrod on Mon May 02, 2005 10:20 am, edited 1 time in total.

 New poster
 Posts: 19
 Joined: Sat Mar 12, 2005 5:56 pm
 Location: Halifax, Nova Scotia, Canada
 Contact:
Try this input:
Your output:
Correct output:
Good luck,
Code: Select all
1
4 5 3
AA AD AC AB
AC AB
AB AD
AC AD
AA AC
AA AB
10 AA AD
10 AA AC
10 AC AD
Code: Select all
SHIPPING ROUTES OUTPUT
DATA SET 1
NO SHIPMENT POSSIBLE
$1000
NO SHIPMENT POSSIBLE
END OF OUTPUT
Code: Select all
SHIPPING ROUTES OUTPUT
DATA SET 1
$2000
$1000
$1000
END OF OUTPUT

 New poster
 Posts: 12
 Joined: Mon Mar 28, 2005 7:55 pm
 Contact:
thanks!!!
Thanks very much. I got AC. I had a very small mistake(result of poor attention), so my code is almost AC and I'd like to remove it as I have seen many have done. How can I do it? Thanks again