## 523 - Minimum Transport Cost

Moderator: Board moderators

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

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

Lucindo

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

### The Problem: Input

I finally solved the problem.... 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

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

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 "10-1" without space...

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

Lucindo

Ivor
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia
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.

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.

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

### Re: Input...

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 "10-1" without space...

This is a multiple input problem too...
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:
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 ?
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

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:
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!

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

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:
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:
Can you give me some detailed information about 'special correction' and 'special judge program'?