523 - Minimum Transport Cost

All about problems in Volume 5. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

lucindo
New poster
Posts: 11
Joined: Thu Sep 05, 2002 2:35 am
Contact:

523 - Minimum Transport Cost

Post by lucindo »

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...
[]'s

Lucindo

lucindo
New poster
Posts: 11
Joined: Thu Sep 05, 2002 2:35 am
Contact:

The Problem: Input

Post by lucindo »

I finally solved the problem.... :D My program was working fine but reading the input wasn
[]'s

Lucindo

Ivor
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia

Post by Ivor »

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

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel »

If you should find the path from i to i, that means to itself, print
Path: i and not Path: i-->i.
And did you notice it is a multiple input problem? I got one time Outputlimit Exceeded :-(

lucindo
New poster
Posts: 11
Joined: Thu Sep 05, 2002 2:35 am
Contact:

Input...

Post by lucindo »

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' :x . Then, read line by line to get the source and destination until a blank line....

Be caerful with "10-1" without space...

This is a multiple input problem too... :D
[]'s

Lucindo

Ivor
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia

Post by Ivor »

If you should find the path from i to i, that means to itself, print
Path: i and not Path: i-->i.
Well that figures. :) It's the only case I hadn't considered. I found my program was printing crap in such a case.

Thanks for your quick answers.
Ivor

P.S. Yeah, I solved my 150th problem. :D
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.

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

Re: Input...

Post by Caesum »

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' :x . Then, read line by line to get the source and destination until a blank line....

Be caerful with "10-1" without space...

This is a multiple input problem too... :D
number 'n' of vertex ? what ? are you sure ? this isnt in the problem description at all. 10-1 without space ? hmm... i have so many asserts in this program its strange nothing fails.......

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski »

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:

Code: Select all

cutted off
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 ....)
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)

tonyk
New poster
Posts: 7
Joined: Mon May 05, 2003 5:11 pm

523 Minimum Transport Cost

Post by tonyk »

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]

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski »

I got the same result ago.
Try to read only first line to '\n' and compute umber of elements. Next N*(N-1) elements read without carry of '\n' :)) because this elements could be in more than N-1 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)

tonyk
New poster
Posts: 7
Joined: Mon May 05, 2003 5:11 pm

I did so!

Post by tonyk »

I did so.
I read only the first line to calculate the value of n, and for the next n-1 line just input the integers. Then the next line input the values of the taxes.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski »

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

Kimi
New poster
Posts: 4
Joined: Sat Oct 18, 2003 4:08 am
Location: Shanghai, China
Contact:

523 Time Limit Exceeded

Post by Kimi »

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

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 »

Are you handling multiple input correctly (green check mark [multiple input and special correction])?

Kimi
New poster
Posts: 4
Joined: Sat Oct 18, 2003 4:08 am
Location: Shanghai, China
Contact:

Post by Kimi »

Can you give me some detailed information about 'special correction' and 'special judge program'? :roll:

Post Reply

Return to “Volume 5 (500-599)”