685 - Least Path Cost

Moderator: Board moderators

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:

685 - Least Path Cost

Can anyone verify the I/O set?

Input:

Code: Select all

``````2
10
9
5
1 2 55
2 3 10
2 9 100
3 9 90
3 4 80
4 5 10
5 6 10
6 7 10
6 8 20
8 9 100
10
9
50
1 2 55
2 3 10
2 9 100
3 9 90
3 4 80
4 5 10
5 6 10
6 7 10
6 8 20
8 9 100``````
Output:

Code: Select all

``````160
385``````
I m getting WA. Is there any trick?

Ami ekhono shopno dekhi...
HomePage

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
I get the same values. I don't remember any tricks, and looking at my code, I can't see anything peculiar; it's basically floyd-warshall from the mid-points of the segments.

Looking at the desciption, I notice that isolated segments can occur in the input, but never in a vaild path. Does your code handle such cases?

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
little joey wrote:Looking at the desciption, I notice that isolated segments can occur in the input, but never in a vaild path. Does your code handle such cases?
Missed that part. Got accepted. . Thanks a lot...
Ami ekhono shopno dekhi...
HomePage

metaphysis
Experienced poster
Posts: 139
Joined: Wed May 18, 2011 3:04 pm

Re: 685 - Least Path Cost

Test data generator:

Code: Select all

``````#include <iostream>
#include <ctime>
#include <cstdlib>
#include <cstring>

using namespace std;

int main(int argc, char *argv[])
{
srand(time(NULL));

int M, N, D, start, end, height, linked[410][410];

int cases = 1000;
cout << cases << '\n';
for (int c = 1; c <= cases; c++)
{
M = rand() % 200 + 1;

do
{
N = rand() % 400 + 1;
} while (N < (M + 50));

D = rand() % 9999 + 1;

cout << M << '\n' << N << '\n' << D << '\n';

for (int i = 1; i <= M; i++)
{
do
{
start = rand() % N + 1, end = rand() % N + 1;

height = rand() % 1000 + 1;
cout << start << ' ' << end << ' ' << height << '\n';
}
}

return 0;
}
``````