10000 - Longest Paths
Moderator: Board moderators
-
- New poster
- Posts: 21
- Joined: Thu Jun 14, 2007 11:45 pm
Two things to change...
Hope it helps.
Code: Select all
void bfs(int s){
....
set all d[i] to 0. // 1st part updated here
while (!fila.empty()){
...
for (v = 1; v <= n; v++){
if (g[u][v] == 1 && d[v] < d[u]+1){ // 2nd part updated here
....
}
}
}
}
Ami ekhono shopno dekhi...
HomePage
HomePage
i have try many input and the output is correct.
but also get WA
can u help me to check it,pls
thz...
but also get WA
can u help me to check it,pls
thz...
Code: Select all
#include <stdio.h>
#include <stdlib.h>
int d[100][100];
int b[100];
int length;
int s;
int max(int a,int b)
{
if (a>b)
return a;
return b;
}
int intial(){
int i,j;
for(i=0;i<=100;i++){
b[i]=-1;
for(j=0;j<=100;j++)
d[i][j]=0;
}
}
void calculate(int k, int n){
int i,j;
if(b[k]==1)
{
for (i=n;i>=1;i--)
if(d[k][i]!=0)
d[s][i]=max(d[s][i],d[s][k]+d[k][i]);
}
if(b[k]==-1){
for (i=n;i>=1;i--){
if(d[k][i]==1)
{
d[s][i]=max(d[s][i],d[s][k]+d[k][i]);
calculate(i,n);
for (j=n;j>=1;j--)
if(d[i][j]!=0)
d[k][j]=max(d[k][j],d[k][i]+d[i][j]);
b[k]=1;
}
}
}
if(b[k]!=1){
b[k]=0;
}
}
int main(){
int t1,t2;
int n,i,j;
int finish;
int count=0;
while(scanf("%d",&n)==1 && n!=0)
{
count++;
intial();
length=0;
scanf("%d",&s);
finish=s;
while(scanf("%d%d",&t1,&t2)==2 && t1!=0 && t2!=0){
d[t1][t2]=1;
}
calculate(s,n);
for(i=1;i<=n;i++){
if(length<d[s][i]){
length=d[s][i];
finish=i;
}
}
printf("Case %d: The longest path from %d has length %d, finishing at %d.\n\n",count,s,length,finish);
}
}
-
- Learning poster
- Posts: 81
- Joined: Wed May 09, 2007 9:59 pm
- Location: (CSE,DU) Dhaka,Bangladesh
CHECK THIS INPUT OUTPUT:
HOPE IT WORKS
Code: Select all
8
8
2 4
3 5
6 8
1 8
5 6
4 7
4 5
5 8
1 5
1 3
2 3
1 7
7 8
3 4
1 2
2 8
2 6
4 6
1 6
6 7
2 7
2 5
5 7
1 4
3 8
3 7
3 6
4 8
0 0
OUTPUT:
Case 9: The longest path from 8 has length 0, finishing at 8.
''I want to be most laziest person in the world''
I tried to solve this problem using Floyd-Warshall but getting wrong.
I think there must be some logical mistake in my code, but I don't know where it is.
This is part of my code.
Somebody please give me some suggestion. Thank you!
I think there must be some logical mistake in my code, but I don't know where it is.
This is part of my code.
Somebody please give me some suggestion. Thank you!
Code: Select all
/*
1. M is zero.
2. In the beginning matrix[i][j] is set to 1 if i and j are connected, set to M otherwise.
3. Before calling this function, all the elements in v[][][] is initialized to false.
4. If the longest path from i to j has to go through k, v[i][j][k] is set to true.
*/
void longest_path(const int& size)
{
for(int k = 0; k < size; k++)
for(int i = 0; i < size; i++)
for(int j = 0; j < size; j++)
if((matrix[i][k] != M) && (matrix[k][j] != M) && (v[i][k][j] == false) && (v[j][k][i] == false) && (i != j) && (j != k) && (k != i))
{
int temp = matrix[i][k] + matrix[k][j];
if(matrix[i][j] < temp)
{
bool k = false;
for(int q = 0; q < size; q++)
if((v[i][k][q] == true) && (v[k][j][q] == true))
{
k = true;
break;
}
if(k == false)
{
matrix[i][j] = matrix[j][i] = temp;
for(int q = 0; q < size; q++)
if((v[i][k][q] == true) || (v[k][j][q] == true))
v[i][j][q] = v[j][i][q] = true;
v[i][j][k] = v[j][i][k] = true;
}
}
}
}
Re: 10000 - Longest Path
any idea why runtime error? can't find any bug....thanks in advance
Code: Select all
#include<stdio.h>
#define max 110
int d[max],source,color[max],indeg[max],tsort[max],adj[max][max];
int n,k,used[max],white=10,grey=11,black=12;
void top_sort()
{
int i,j,l;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(indeg[j]==0&&used[j]==0)
{
tsort[k++]=j;
used[j]=1;
for(l=1;l<=n;l++)
{
if(adj[j][l]==1)
{
indeg[l]--;
}
}
}
}
}
}
void bfs()
{
int i,j,temp,u,v,q[110],f,r,count=0;
for(i=1;i<=n;i++)
{
color[i]=white;
d[i]=0;
}
color[source]=grey;
temp=source;
f=1;
r=1;
q[f]=source;
r++;
while(r!=f)
{
u=q[f];
f++;
for(v=1;v<=n;v++)
{
if(adj[u][tsort[v]]==1)
{
if(color[tsort[v]]==white||d[u]>=d[tsort[v]])
{
color[tsort[v]]=grey;
d[tsort[v]]=d[u]+1;
q[r]=tsort[v];
r++;
}
}
}
}
}
int main()
{
int i,j,p,q,maxx=0,dest,c=0;
// freopen("10000.txt","rt",stdin);
while(scanf("%d",&n)==1)
{
if(n==0)
break;
scanf("%d",&source);
for(i=1;i<=n;i++)
{
indeg[i]=0;
used[i]=0;
for(j=1;j<=n;j++)
{
adj[i][j]=0;
}
}
while(scanf("%d %d",&p,&q)==2)
{
if(p==0&&q==0)
break;
adj[p][q]=1;
indeg[q]++;
}
k=1;
top_sort();
bfs();
maxx=0;
for(i=1;i<=n;i++)
{
if(d[i]>maxx)
{
maxx=d[i];
dest=i;
}
}
if(maxx==0)
dest=source;
printf("Case %d: The longest path from %d has length %d, finishing at %d.\n\n",++c,source,maxx,dest);
}
return 0;
}
Re: 10000 - Longest Path
Hi, I'm getting wrong answer with this code, could you tell me what's my mistake?
Code: Select all
#include<iostream>
#include<queue>
#include<map>
using namespace std;
int n,s;
int longest;
int destiny;
int visited[101];
vector< vector<int> > L(101);
void bfs(){
queue< pair<int,int> > Q;
Q.push(make_pair(s,0));
pair<int,int> aux;
while(!Q.empty()){
aux=Q.front();
Q.pop();
if(aux.second>visited[aux.first]){
visited[aux.first]=aux.second;
if(aux.second>longest){
longest=aux.second;
destiny=aux.first;
}else if(aux.second==longest && aux.first<destiny) destiny=aux.first;
for(int i=0;i<L[aux.first].size();i++)
Q.push(make_pair(L[aux.first][i],aux.second+1));
}
}
}
int main(){
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
int caso=1,p,q;
while(1){
scanf("%d",&n);
if(n==0) break;
scanf("%d",&s);
for(int i=0;i<n;i++) L[i].clear();
while(1){
scanf("%d %d",&p,&q);
if(p==0 && q==0) break;
L[p].push_back(q);
}
destiny=s;
longest=0;
memset(visited,-1,sizeof(visited));
bfs();
cout<<"Case "<<caso<<": The longest path from "<<s<<" has length "<<longest<<", finishing at "<<destiny<<"."<<endl<<endl;
caso++;
}
return 0;
}
-
- Experienced poster
- Posts: 103
- Joined: Tue Mar 25, 2008 11:00 pm
- Location: IUT-OIC, DHAKA, BANGLADESH
- Contact:
Re: 10000 - Longest Path(15 time WA)
I have checked all of the inputs of this topic(all of 9 pages).but getting correct answer. i generate random numbers.although i got correct answer(checked at uvatoolkit)..still now i didnt get where is the bug.
i used floyed warshall and assumed
1. the graph is directed.
2.if source and destination is same then length is 0.
3.repeatedly checked code and submited.but in vain.....
pliz who have solved,,,,help.here is my code.
i used floyed warshall and assumed
1. the graph is directed.
2.if source and destination is same then length is 0.
3.repeatedly checked code and submited.but in vain.....
pliz who have solved,,,,help.here is my code.
Code: Select all
#include<iostream>
#include<algorithm>
using namespace std;
#define mx 210
#define inf 32767
int m[mx][mx],mm[mx][mx],path[mx][mx],n,u,v,t;
void floyed(){
int i,j,k;
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(m[i][k]!=inf&&m[k][j]!=inf){
m[i][j]=m[i][k]+m[k][j],mm[i][j]=mm[i][k]+mm[k][j],path[i][j]=path[i][k];
}
}
int main(){
int i,j,kk=0;
//freopen("1.txt","r",stdin);
while(cin>>n>>u&&n){
fill(m[0],m[n+1],inf);
fill(mm[0],mm[n+1],0);
while(cin>>i>>j&&(i||j)){
m[i][j]=1;
mm[i][j]=1;
}
floyed();
v=0;
int I=u;
for(i=1;i<=n;i++){
if(i==u)continue;
if(v<mm[u][i])v=mm[u][i],I=i;
}
cout<<"Case "<<++t<<": The longest path from "<<u<<" has length "<<v<<", finishing at "<<I<<".\n\n";
}
return 0;
}
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................
It is more tough to become a good person.
I am trying both...............................
-
- New poster
- Posts: 7
- Joined: Mon Dec 22, 2008 3:00 pm
Re: 10000 - Longest Path
I am getting Runtime error please help
#include<stdio.h>
#include<stdlib.h>
struct node{
int value;
struct node * next;
};
int numNodes;
int largestDepth;
VISIT(struct node **Node, int n){
static int depth=0;
struct node *NODE = Node[n];
while(NODE!=0){
++depth;
VISIT(Node,NODE->value);
NODE=NODE->next;
}
if(depth>largestDepth)
largestDepth=depth;
depth=0;
}
int main(void){
int caseNo=1;
while(1){
int startNode;
scanf("%d",&numNodes);
if(numNodes<1)break;
scanf("%d",&startNode);
struct node *Node[numNodes+1];
int i;
for(i=1;i<numNodes+1;i++){
Node=0;
}
int p,q;
while(1){
scanf("%d",&p);
scanf("%d",&q);
if(p==0 && q==0)
break;
if(Node[p]==0){
Node[p] = (struct node *)malloc(sizeof (struct node));
Node[p]->value=q;
Node[p]->next=0;
}else{
struct node * head=Node[p];
while(head->next!=0){
head=head->next;
}
struct node * new= (struct node *)malloc(sizeof (struct node));
new->value=q;
new->next=head;
head->next=new;
new->next=0;
}
}
VISIT(Node,startNode);
printf("Case %d: The longest path from %d has length %d finishing at %d.\n",caseNo,startNode, largestDepth,2); // yet to implement smallest node among the same longest length using 2 here
largestDepth=0;
caseNo++;
}
}
#include<stdio.h>
#include<stdlib.h>
struct node{
int value;
struct node * next;
};
int numNodes;
int largestDepth;
VISIT(struct node **Node, int n){
static int depth=0;
struct node *NODE = Node[n];
while(NODE!=0){
++depth;
VISIT(Node,NODE->value);
NODE=NODE->next;
}
if(depth>largestDepth)
largestDepth=depth;
depth=0;
}
int main(void){
int caseNo=1;
while(1){
int startNode;
scanf("%d",&numNodes);
if(numNodes<1)break;
scanf("%d",&startNode);
struct node *Node[numNodes+1];
int i;
for(i=1;i<numNodes+1;i++){
Node=0;
}
int p,q;
while(1){
scanf("%d",&p);
scanf("%d",&q);
if(p==0 && q==0)
break;
if(Node[p]==0){
Node[p] = (struct node *)malloc(sizeof (struct node));
Node[p]->value=q;
Node[p]->next=0;
}else{
struct node * head=Node[p];
while(head->next!=0){
head=head->next;
}
struct node * new= (struct node *)malloc(sizeof (struct node));
new->value=q;
new->next=head;
head->next=new;
new->next=0;
}
}
VISIT(Node,startNode);
printf("Case %d: The longest path from %d has length %d finishing at %d.\n",caseNo,startNode, largestDepth,2); // yet to implement smallest node among the same longest length using 2 here
largestDepth=0;
caseNo++;
}
}
Re: 10000 - Longest Path
Use [code]...[/code] to post code.
If you submit your program as C, one of the reasons of a runtime error verdict can be a non-zero exit code. Make sure that your main() returns 0.
Also, it seems like you're missing commas in the output, and don't print newlines between outputs for different cases. You'd get WA for that - judge expects your program's output to be byte-wise equal to a reference solution's output.
If you submit your program as C, one of the reasons of a runtime error verdict can be a non-zero exit code. Make sure that your main() returns 0.
Also, it seems like you're missing commas in the output, and don't print newlines between outputs for different cases. You'd get WA for that - judge expects your program's output to be byte-wise equal to a reference solution's output.
-
- New poster
- Posts: 7
- Joined: Mon Dec 22, 2008 3:00 pm
Re: 10000 - Longest Path
Thanks , Now I am getting TL error is there any standard algo for this type of problem
-
- Learning poster
- Posts: 78
- Joined: Sun Nov 30, 2008 5:00 pm
- Location: IUT-OIC, Dhaka, Bangladesh
Re: 10000 - Longest Path
You can use BFS to find the longest path. I used that and got AC.
May be tomorrow is a better day............ ![:)](./images/smilies/icon_smile.gif)
![:)](./images/smilies/icon_smile.gif)