685 - Least Path Cost

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

Moderator: Board moderators

Post Reply
Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

685 - Least Path Cost

Post by Jan » Tue May 01, 2007 9:17 pm

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?

Thanks in advance.
Ami ekhono shopno dekhi...
HomePage

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Thu May 03, 2007 1:30 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
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Thu May 03, 2007 1:38 pm

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

Post by metaphysis » Sat Jun 10, 2017 2:24 pm

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';
        
        memset(linked, 0, sizeof(linked));
        for (int i = 1; i <= M; i++)
        {
            do
            {
                start = rand() % N + 1, end = rand() % N + 1;
            } while (start == end || linked[start][end] || linked[end][start]);
            
            linked[start][end] = linked[end][start] = 1;
            height = rand() % 1000 + 1;
            cout << start << ' ' << end << ' ' << height << '\n';
        }
    }
    
    return 0;
}

Post Reply

Return to “Volume 6 (600-699)”