11015 - 05-2 Rendezvous
Moderator: Board moderators
Re: help me
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);
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);
Thanks
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)
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...
-
- New poster
- Posts: 13
- Joined: Thu May 26, 2005 1:16 pm
11015 - 05-2 Rendezvous
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?
---> It causes no one can arrive Hecotr's home!
(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
my program produce the following output for your input:
bye
Code: Select all
Case #1 : John
-
- New poster
- Posts: 13
- Joined: Thu May 26, 2005 1:16 pm
-
- New poster
- Posts: 13
- Joined: Thu May 26, 2005 1:16 pm
Yes , I used a matrix to store the graph and set all graph[j] = 0SRX wrote: hi , I read my program again and I found one thing .
does your execution maintain dis(i,i)=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
![:(](./images/smilies/icon_frown.gif)
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;
}
Code: Select all
int* min_dist(int N,int** graph,int k)
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 ......
![:(](./images/smilies/icon_frown.gif)
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];
}
-
- New poster
- Posts: 13
- Joined: Thu May 26, 2005 1:16 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.
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.
-
- New poster
- Posts: 13
- Joined: Thu May 26, 2005 1:16 pm
Test cases
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:
Thanks!!
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;
}
-
- New poster
- Posts: 1
- Joined: Fri Mar 09, 2007 8:49 am
I use Dijkstra and got WA.
Could someone give me some test cases or check my Dijkstra for me please?
Thanks in advance.
I set DIS_MAX to 50000, would the value affects the result?
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
}