It is also given that in case of a tie, a smaller indexed vertex should be preferable to a larger indexed vertex.
First in my approach i traversed graph using bfs finding distances of all vertices from start node ,i got the path length from start to end node,then i traversed from end node to start node by viewing if the length of node is one less than previous,but i am missing some point in between when i submit my code it is not correct for all test cases,please can someone find what is my mistake. -
#include <stdio.h>
-
#include <stdlib.h>
-
-
int count=0;
-
-
struct node{
-
-
int value;
-
struct node *next;
-
struct node *prev;
-
};
-
-
struct node *root=NULL,*tra=NULL;
-
-
void bfs(int n,int a[][n],int start,int end,int value[]){
-
-
for(int i=0;i<n ;i++){
-
-
if(i==start)
-
continue;
-
-
if(a[start][i] == 1 ){
-
-
-
if(value[i] == 0 || value[i] > value[start] + 1 ){
-
-
value[i] = value[start] + 1;
-
-
struct node *p;
-
-
p = (struct node *)malloc(sizeof(struct node));
-
p->value = i;
-
p->next = root;
-
p->prev = NULL;
-
root->prev = p;
-
-
root = p;
-
}
-
}
-
}
-
-
return;
-
}
-
-
int main()
-
{
-
int t;
-
scanf("%d",&t);
-
-
for(int i=0;i<t;i++){
-
-
int n;
-
scanf("%d",&n);
-
-
int a[n][n],start,end,value[n];
-
struct node *temp;
-
-
for(int j=0;j<n;j++){
-
for(int k=0;k<n;k++){
-
scanf("%d",&a[j][k]);
-
}
-
}
-
-
-
memset(value,0,n*4);
-
scanf("%d %d",&start,&end);
-
-
value[start]=1;
-
-
temp = (struct node *)malloc(sizeof(struct node));
-
temp->value = start;
-
temp->next = NULL;
-
temp->prev = NULL;
-
-
root = temp;
-
tra = temp;
-
-
-
while(tra != NULL){
-
-
bfs(n,a,tra->value,end,value);
-
tra = tra->prev;
-
}
-
-
printf("%d\n",value[end]-1);
-
-
int x = end;
-
-
int p[n],pi=0;
-
p[pi++] = x;
-
-
while(1){
-
-
for(int j=0;j<n;j++){
-
if((value[j] == value[x]-1) &&(a[j][x] == 1)){
-
// printf("%d ",j);
-
p[pi++] = j;
-
-
x=j;
-
break;
-
-
}
-
}
-
if(x == start){
-
break;
-
}
-
-
}
-
-
for(int j=pi-1;j>=0;j--){
-
printf("%d ",p[j]);
-
-
}
-
}
-
return 0;
-
}
-
0 1193 Sign in to post your reply or Sign up for a free account.
Similar topics
by: Job Lot |
last post by:
How can I find path of windows folder using vb.net? It could be winnt or
windows depending upon the os.
System.Environment.SpecialFolder enumeration does not have a constant for
windows folder.
|
by: srinivas |
last post by:
Hi all,
I have one requirement.Is there any way to create a line graph
using javascript.If it is please send me the sample code.But the thing
is it should work in all browsers.
Thanks,...
|
by: ANUPAM |
last post by:
Hi All,
I have to show Tooltip for Bar/Pie graph using MS charts control in C#
which is not available while it is in Visual Basic Version.
Please help me.
Thansks All,
Anupam
|
by: Syazwin |
last post by:
Hye everyone! :)
i am really a new learner in vb.net. not so expert about what i am searching now.. actually i am looking for the way/source code how to make a line graph in vb.net. the system...
|
by: suedasszyy |
last post by:
Haiiii....
i'm new for VB.net.
can someone help me to solve those question?
is it possible to draw a graph such as Sin graph using console application?
if not,
how can i draw a graph...
|
by: sainiamit25 |
last post by:
Hi,
I need to make a graph using javascript based on the values in the oracle table. Can somebody throw some on it?
Thanks in advance for your help,
Amit
|
by: cmrhema |
last post by:
Hi,
My client will input two values say A and B.
Here A and B represent cities. The source is A and the Destination is B
Now i have to find the shortest route for these two cities
One is using...
|
by: gubbachchi |
last post by:
Hi all,
I have got a problem with plotting bar graph using GD. I am learning GD now.
I have written the code for basic bar graph with one bar. What I need is, scale on Y-axis i.e. divisions on...
|
by: acheng |
last post by:
I want to plot a 3D graph using MathGL. There are three variables (X,Y,Z), and kinds of combination correspond different C values. Also C vector sets the color scheme. I write some codes as below....
|
by: 123pavi |
last post by:
Any pointers to algorithms to find "Fundamental Cutsets of a graph or a tree"
|
by: DolphinDB |
last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation.
Take...
|
by: DolphinDB |
last post by:
Tired of spending countless mintues downsampling your data? Look no further!
In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
|
by: ryjfgjl |
last post by:
ExcelToDatabase: batch import excel into database automatically...
|
by: isladogs |
last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM).
In this month's session, we are pleased to welcome back...
|
by: ArrayDB |
last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
|
by: PapaRatzi |
last post by:
Hello,
I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
|
by: Defcon1945 |
last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
|
by: af34tf |
last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
|
by: Faith0G |
last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
| |