523 - Minimum Transport Cost

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

[lucindo]

I finally solved the problem.... My program was working fine but reading the input wasn

[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

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

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

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

[Caesum]

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]

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

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

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

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

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

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

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

[Kimi]

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