523  Minimum Transport Cost
Moderator: Board moderators
523  Minimum Transport Cost
I'm trying to solve the problem 523 using djikstra algorithm. What I should print when there is no way from c to d???
Using Floyd I got WA too.
I read the comments of the problem and I thing my program is working fine for the (ugly) input.
Anyone can send me a input/output sample???
Thanks...
Using Floyd I got WA too.
I read the comments of the problem and I thing my program is working fine for the (ugly) input.
Anyone can send me a input/output sample???
Thanks...
[]'s
Lucindo
Lucindo
The Problem: Input
I finally solved the problem.... My program was working fine but reading the input wasn
[]'s
Lucindo
Lucindo
Would you please share your thoughts about this problem... I seem to having trouble with it. I believe I have Dijkstra modified correctly, however I'm not sure about input/output...
Ivor
Ivor
There is a theory which states that if ever anyone discovers exactly what the Universe is for and why it is here, it will instantly disappear and be replaced by something even more bizarre and inexplicable.

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
Input...
First read a line to find out the number 'n' of vertex. After that, you must read n^2 numbers, ignoring aditionals or unexpected '\n' . Then, read line by line to get the source and destination until a blank line....
Be caerful with "101" without space...
This is a multiple input problem too...
Be caerful with "101" without space...
This is a multiple input problem too...
[]'s
Lucindo
Lucindo
Well that figures. It's the only case I hadn't considered. I found my program was printing crap in such a case.If you should find the path from i to i, that means to itself, print
Path: i and not Path: i>i.
Thanks for your quick answers.
Ivor
P.S. Yeah, I solved my 150th problem.
There is a theory which states that if ever anyone discovers exactly what the Universe is for and why it is here, it will instantly disappear and be replaced by something even more bizarre and inexplicable.
Re: Input...
number 'n' of vertex ? what ? are you sure ? this isnt in the problem description at all. 101 without space ? hmm... i have so many asserts in this program its strange nothing fails.......lucindo wrote:First read a line to find out the number 'n' of vertex. After that, you must read n^2 numbers, ignoring aditionals or unexpected '\n' . Then, read line by line to get the source and destination until a blank line....
Be caerful with "101" without space...
This is a multiple input problem too...

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
Could anyone tell me, why this program gets RTE ?
I'm really don't know, why  I test it in many possible and impossible ways and cannot found my mistake (( Maybe I forgot about something ?
Please , help me !
I hate to post code ... but I don't know what's wrong I got 7 RTE ....
Dominik Michniewski
The source is:
I got Accepted, when I rewrite code .... but I think, that's no fair if given for us data is out of specification (I really think, that empty lines exist in this IO not only as separators of data sets ....)
I'm really don't know, why  I test it in many possible and impossible ways and cannot found my mistake (( Maybe I forgot about something ?
Please , help me !
I hate to post code ... but I don't know what's wrong I got 7 RTE ....
Dominik Michniewski
The source is:
Code: Select all
cutted off
If you really want to get Accepted, try to think about possible, and after that  about impossible ... and you'll get, what you want ....
Born from ashes  restarting counter of problems (800+ solved problems)
Born from ashes  restarting counter of problems (800+ solved problems)
523 Minimum Transport Cost
Why I got Run Time Error?? Help!!
[cpp]#include <iostream>
#include <vector>
using namespace std;
int city[1024][1024], path[1024][1024], tax[1024];
vector<int> p;
vector<int>::iterator pnt;
void store_path(int i, int j)
{
int k=path[j];
if(k!=1)
{
store_path(i,k);
p.push_back(k);
store_path(k,j);
}
}
int main() {
int i=1, j=1, k, n=0;
char c;
while(cin>>city[j])
{
j++; n++;
c=cin.get();
if(c=='\n') break;
}
for(i=2; i<=n; i++)
for(j=1; j<=n; j++)
cin >> city[j];
for(i=1; i<=n; i++)
cin >> tax;
for(i=1; i<=n; i++)
for(j=1; j<=n; j++) {
if(city[j] == 1)
city[j] = 10000;
path[j]=1;
}
for(k=1; k<=n; k++)
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
if((city[k] + city[k][j] + tax[k]) < city[j])
{
city[j] = city[i][k] + city[k][j] + tax[k];
path[i][j]=k;
}
while(cin >> i >> j)
{
cout << "From " << i << " to " << j << " :" << endl;
if(i==j) cout << "Path: " << i << endl;
else {cout << "Path: " << i;
store_path(i, j);
for(pnt=p.begin();pnt!=p.end();pnt++)
cout << ">" << *pnt ;
cout << ">" << j << endl;
p.clear();
}
cout << "Total cost : " << city[i][j] << endl << endl;
}
return 0;
}
[/cpp]
[cpp]#include <iostream>
#include <vector>
using namespace std;
int city[1024][1024], path[1024][1024], tax[1024];
vector<int> p;
vector<int>::iterator pnt;
void store_path(int i, int j)
{
int k=path[j];
if(k!=1)
{
store_path(i,k);
p.push_back(k);
store_path(k,j);
}
}
int main() {
int i=1, j=1, k, n=0;
char c;
while(cin>>city[j])
{
j++; n++;
c=cin.get();
if(c=='\n') break;
}
for(i=2; i<=n; i++)
for(j=1; j<=n; j++)
cin >> city[j];
for(i=1; i<=n; i++)
cin >> tax;
for(i=1; i<=n; i++)
for(j=1; j<=n; j++) {
if(city[j] == 1)
city[j] = 10000;
path[j]=1;
}
for(k=1; k<=n; k++)
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
if((city[k] + city[k][j] + tax[k]) < city[j])
{
city[j] = city[i][k] + city[k][j] + tax[k];
path[i][j]=k;
}
while(cin >> i >> j)
{
cout << "From " << i << " to " << j << " :" << endl;
if(i==j) cout << "Path: " << i << endl;
else {cout << "Path: " << i;
store_path(i, j);
for(pnt=p.begin();pnt!=p.end();pnt++)
cout << ">" << *pnt ;
cout << ">" << j << endl;
p.clear();
}
cout << "Total cost : " << city[i][j] << endl << endl;
}
return 0;
}
[/cpp]

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
I got the same result ago.
Try to read only first line to '\n' and compute umber of elements. Next N*(N1) elements read without carry of '\n' ) because this elements could be in more than N1 lines .... that's strange, but I got Acc in this way
Best regards
DM
Try to read only first line to '\n' and compute umber of elements. Next N*(N1) elements read without carry of '\n' ) because this elements could be in more than N1 lines .... that's strange, but I got Acc in this way
Best regards
DM
If you really want to get Accepted, try to think about possible, and after that  about impossible ... and you'll get, what you want ....
Born from ashes  restarting counter of problems (800+ solved problems)
Born from ashes  restarting counter of problems (800+ solved problems)

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
Could you test it with matrixes 1x1 ?
or greater than 1024 elements ?
or when matrix is NxN, and query is for N+k ?
I think, that must exist case in which you are going out of tables or vectors sizes ....
DM
PS. It's multiply input problem ....
or greater than 1024 elements ?
or when matrix is NxN, and query is for N+k ?
I think, that must exist case in which you are going out of tables or vectors sizes ....
DM
PS. It's multiply input problem ....
If you really want to get Accepted, try to think about possible, and after that  about impossible ... and you'll get, what you want ....
Born from ashes  restarting counter of problems (800+ solved problems)
Born from ashes  restarting counter of problems (800+ solved problems)
523 Time Limit Exceeded
I use 'Floyd' algorithm(O(n^3)) for this problem, but i got a TLE.
I wonder if there is any better algorithm for it?
and also, they don't declare how big is the data size(n, I mean).
I wonder if there is any better algorithm for it?
and also, they don't declare how big is the data size(n, I mean).