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 » Thu Sep 05, 2002 2:55 am

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 » Mon Sep 09, 2002 2:25 pm

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 » Tue Sep 10, 2002 3:08 pm

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 » Tue Sep 10, 2002 7:03 pm

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 » Tue Sep 10, 2002 9:43 pm

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 » Wed Sep 11, 2002 11:04 am

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 » Tue Jan 21, 2003 8:04 pm

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 » Tue Feb 11, 2003 10:01 am

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 » Wed May 07, 2003 4:53 pm

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 » Thu May 08, 2003 8:21 am

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 » Thu May 08, 2003 10:51 am

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 » Thu May 08, 2003 12:37 pm

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 » Sat Oct 18, 2003 4:24 am

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

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

Post by UFP2161 » Sat Oct 18, 2003 5:06 am

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 » Sat Oct 18, 2003 10:14 am

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

Post Reply

Return to “Volume 5 (500-599)”