11015 - 05-2 Rendezvous

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

Moderator: Board moderators

User avatar
mute
New poster
Posts: 8
Joined: Thu Apr 13, 2006 2:16 am
Location: Dhaka
Contact:

Re: help me

Post by mute » Mon Jul 24, 2006 12:27 pm

Hello tuman(sedin tor code ta thik moto kheal kori nai),
After calling "fw(adj,a)" when you are finding the min you must make the Diagonal part '0' of your "adj"

add
for(i=1; i<=a; i++) adj = 0;
after calling fw(adj,a);
Check this out ThirdEye Creative.com
Image

User avatar
tuman
New poster
Posts: 24
Joined: Sat Oct 22, 2005 7:30 pm
Location: CUET
Contact:

Thanks

Post by tuman » Wed Jul 26, 2006 6:33 pm

Thanx guys ,
it was a silly mistake, i forgot to assign 0 diagonally.
macko this problem does not need multiple edges. From the problem statement it was unclear that whether it consists multiple edges or not.
I got accepted without multiple edge and also with multiple edges.


//(Nafi ...censor.... tui ei simple jinish ta dekhte ato time lagali !!! LOL)
We the dreamer of the dreamy dream...

Hector_Hsu
New poster
Posts: 13
Joined: Thu May 26, 2005 1:16 pm

11015 - 05-2 Rendezvous

Post by Hector_Hsu » Wed Aug 16, 2006 11:25 am

I tried to solve this problem with Dijkstra's Algorithm N times.
(I know there is a better way.... but I just try it...)

But WA so many times, can anyone send me some critical test cases?

I've read the previous posts already.

btw,

Will the following output appears?

Code: Select all

3 1
Hector
John
Ray
2 3 1
---> It causes no one can arrive Hecotr's home!

DP
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Location: Bangladesh
Contact:

Post by DP » Wed Aug 16, 2006 11:48 am

my program produce the following output for your input:

Code: Select all

Case #1 : John
bye

Hector_Hsu
New poster
Posts: 13
Joined: Thu May 26, 2005 1:16 pm

Post by Hector_Hsu » Wed Aug 16, 2006 11:55 am

My prog outputs the same..

any other inputs~? plz >"<

SRX
Learning poster
Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan

Post by SRX » Wed Aug 16, 2006 2:56 pm

Hector_Hsu wrote:My prog outputs the same..

any other inputs~? plz >"<
hi , I read my program again and I found one thing .

does your execution maintain dis(i,i)=0 ?
studying @ ntu csie

Hector_Hsu
New poster
Posts: 13
Joined: Thu May 26, 2005 1:16 pm

Post by Hector_Hsu » Wed Aug 16, 2006 3:29 pm

SRX wrote: hi , I read my program again and I found one thing .

does your execution maintain dis(i,i)=0 ?
Yes , I used a matrix to store the graph and set all graph[j] = 0
So if there is no input about house I to house J , the distance between them will be zero.(not connected)

---------------------------------------------------------------------------------

My main function :(Excuse me for using dynamic memory....)

Code: Select all

int main(void)
{
    int N,M,I,J,K,**graph,*dist,*d,min,ans,cas=0;
    char **name;
    while(cin>>N>>M)
    {
        cas++;
        if(!N)
            break;
        graph = new int*[N];
        for(int i=0;i<N;i++)
            graph[i] = new int[N];
        for(int i=0;i<N;i++)
            for(int j=0;j<N;j++)
                graph[i][j] = 0;
        dist = new int[N];
        for(int i=0;i<N;i++)
            dist[i] = 0;
        name = new char*[N];
        for(int i=0;i<N;i++)
        {
            name[i] = new char[11];
            cin>>name[i];
        }
        for(int i=0;i<M;i++)
        {
            cin>>I>>J>>K;
            graph[I-1][J-1] = graph[J-1][I-1] = K;
        }
        for(int i=0;i<N;i++)
        {
            d = min_dist(N,graph,i);
            for(int j=0;j<N;j++)
                dist[j] += d[j];
        }
        min = dist[0];
        ans = 0;
        for(int i=1;i<N;i++)
        {
            if(dist[i]<min)
            {
                ans = i;
                min = dist[i];
            }
        }
        cout<<"Case #"<<cas<<" : "<<name[ans]<<endl;
        for(int i=0;i<N;i++)
        {
            delete graph[i];
            delete name[i];
        }
        delete graph;
        delete name;
    }
    return 0;
}
The function called is

Code: Select all

int* min_dist(int N,int** graph,int k)
which is a Dijkstra's Algorithm,
return an array , which gives the length of shortest paths from house k.


Is there any bug in the main function?

Or ...

I should check my Dijkstra's ...... :(

DP
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Location: Bangladesh
Contact:

Post by DP » Wed Aug 16, 2006 3:42 pm

can you explain this code segment---->

Code: Select all

        for(int i=0;i<N;i++)
        {
            d = min_dist(N,graph,i);
            for(int j=0;j<N;j++)
                dist[j] += d[j];
        } 

Hector_Hsu
New poster
Posts: 13
Joined: Thu May 26, 2005 1:16 pm

Post by Hector_Hsu » Wed Aug 16, 2006 5:36 pm

DP:

Take a example, assume there are 5 nodes.

A,B,C,D,E

The program will run five times , k = A to E

for k = A:

Begin with node A , use Dijkstra's to travel the graph
then I get the shortest paths to B,C,D,E
that 4 value will be added to the dist

after k = E done.

=>

dist will store the total distance to house i.

compare all dist and find the min one to output.

Hector_Hsu
New poster
Posts: 13
Joined: Thu May 26, 2005 1:16 pm

Post by Hector_Hsu » Wed Aug 16, 2006 5:42 pm

And finally I get Accepted. :D

The bug is that when I implement my Dijkstra's algorithm,

I use "heap" to be a min-priority queue.

And I forget to maintain the min-priority property everytime I make some action to the heap......

It's just a silly mistake....but I think it is easily to be ignored....^^"

mhayter1
New poster
Posts: 15
Joined: Wed Jul 26, 2006 10:00 am

Test cases

Post by mhayter1 » Sat Jan 13, 2007 11:02 pm

Could someone give me some test cases for this problem. Apparently I don't understand the problem. I'm also a newbie when it comes to algos.
I out which algo to use, which is a big success, but I not getting AC.

Here's my code:

Code: Select all

/*
ID:mhayter1
PROG:ride
LANG:C++
*/
#include <iostream>
#include <fstream>
#include <vector>
#include <cctype>
#include <cstdio>
#include <iomanip>
#include <string>
#include <algorithm>
#include <sstream>
using namespace std;

/*
ifstream fin(".in");
ofstream fout(".out");
*/

const int INFINITY=1010;

int main()
{
    int distance[30][30];
    int n,m;
    string array[30];
    for(int cases=1;cin>>n>>m;cases++)
    {
        if(n==0 && m==0)
            break;
        for(int i=0;i<25;i++)
        {
            for(int j=0;j<25;j++)
            {
                distance[i][j]=INFINITY;
            }
        }
        for(int i=0;i<n;i++)
        {
            cin>>array[i+1];
        }
        int u,v,w;
        for(int i=0;i<m;i++)
        {
            cin>>u>>v>>w;
            distance[u][v]=distance[v][u]=w;
        }
        for(int k=1;k<=n;k++)
        {
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    if(distance[i][k]+distance[k][j]<distance[i][j])
                    {
                        distance[i][j]=distance[i][k]+distance[k][j];
                    }
                }
            }
        }
        int minsum=23*INFINITY;
        int cursum=0;
        int where=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                cursum+=distance[i][j];
            }
            if(cursum<minsum)
            {
                minsum=cursum;
                where=i;
            }
            cursum=0;
        }
        cout<<"Case #"<<cases<<" : "<<array[where]<<endl;
    }
    int y;
    cin>>y;
    return 0;
}
Thanks!!

mhayter1
New poster
Posts: 15
Joined: Wed Jul 26, 2006 10:00 am

Post by mhayter1 » Fri Jan 19, 2007 3:06 am

Could someone please give me test cases or something. Please :D

deception01
New poster
Posts: 1
Joined: Fri Mar 09, 2007 8:49 am

Post by deception01 » Mon Apr 09, 2007 5:08 am

i'm not sure why you'd use dijkstra's when floyd's seems so much more appropriate and easier
---
Kshitij.

User avatar
Spykaj
New poster
Posts: 47
Joined: Sun May 21, 2006 12:13 pm

Post by Spykaj » Mon Apr 09, 2007 1:48 pm

Floyd is enough.

User avatar
WingletE
New poster
Posts: 35
Joined: Sun Aug 13, 2006 1:34 pm
Location: Taipei, Taiwan
Contact:

Post by WingletE » Tue Aug 28, 2007 4:01 pm

I use Dijkstra and got WA.
Could someone give me some test cases or check my Dijkstra for me please?
Thanks in advance.

Code: Select all

int dijkstra(const int dis[22][22], const int& m, const int& start_p)
{
    int dis_min[m];          //  minimun distance
    bool not_vis[m];         //  haven't visited
    
    fill(dis_min, dis_min+m, DIS_MAX);
    fill(not_vis, not_vis+m, true);
    dis_min[start_p] = 0;
    
    for(int j = 0; j < m; j++)
    {
        int ptr = -1, min = DIS_MAX;
        
        for(int i = 0; i < m; i++)
            if((not_vis[i] == true)&&(min > dis_min[i]))
                min = dis_min[i], ptr = i;
        
        if(ptr == -1)
            break;
        
        for(int i = 0; i < m; i++)
            if(dis_min[ptr] + dis[ptr][i] < dis_min[i])
                dis_min[i] = dis_min[ptr] + dis[ptr][i];
        
        not_vis[ptr] = false;
    }
    
    int sum = 0;
    
    for(int i = 0; i < m; i++)
        sum += dis_min[i];
    
    return sum;              //  the shortest path start from start_p
}
I set DIS_MAX to 50000, would the value affects the result?

Post Reply

Return to “Volume 110 (11000-11099)”