383 - Shipping Routes

[titid_gede]

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]

[titid_gede]

anyone can help me? i still cannot find my mistakes

[Junayeed]

I use BFS to solve this problem. But I am getting WA. Can any one help me with some tricky input. And what will be the output for this input

2
6 7 5
AA CC QR FF DD AB
AA CC
CC QR
DD CC
AA DD
AA AB
DD QR
AB DD
0 AA AB
14 DD CC
1 CC DD
2 AA FF
13 AB QR
3 0 1
AA BB CC
5 AA CC


Thanks

[UFP2161]

That's just the sample input, so the output would be the sample output. By the way, you can use Floyd-Warshall to generate the minimum lengths between any two warehouses, and not have to do a BFS for each shipping request. Probably less error prone too.

[Junayeed]

This is the sample i/p but with slight change. Thats why i gave this i/p.
Any way thanks a lot for the reply. Please give me the o/p for the above i/p.

Thanks a lot

[UFP2161]

Whoops, sorry, I didn't see that one of the numbers changed to a 0. Well, obviously, if you don't ship anything, it costs nothing. So, the answer to "0 AA AB" is "$0". All other queries remain unchanged.

[b3yours3lf]

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??

[technobug]

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

[howa]

[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?

[howa]

help~

[jackie]

After 5 PEs i get AC.

Just output like the sample output.

But pay attention to the case p = 0

After "DATA SET n" there is one blank line, after p lines answer there is also one blank line. Consider the case p = 0, only one blank line should be output.

hope it can help

good luck.

[Minilek]

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]

[Lord Nemrod]

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...

[sahand]

Try this input:

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

Your output:

Code: Select all

SHIPPING ROUTES OUTPUT

DATA SET  1

NO SHIPMENT POSSIBLE
$1000
NO SHIPMENT POSSIBLE

END OF OUTPUT

Correct output:

Code: Select all

SHIPPING ROUTES OUTPUT

DATA SET  1

$2000
$1000
$1000

END OF OUTPUT

Good luck,

[Lord Nemrod]

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