Page 9 of 11
Posted: Mon Aug 13, 2007 9:14 pm
by renato_ferreira
Can I say that if a vertex is on the queue, it don't need to go again?
Because I tried to do it, and got WA.
Posted: Mon Aug 13, 2007 10:44 pm
by Jan
Two things to change...
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
....
}
}
}
}
Hope it helps.
Posted: Tue Aug 14, 2007 1:09 am
by renato_ferreira
Thank you very much, AC!
Posted: Sat Jan 05, 2008 9:01 pm
by jj_99
i have try many input and the output is correct.
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);
}
}
Posted: Sat Feb 23, 2008 8:55 pm
by turcse143
CHECK THIS INPUT OUTPUT:
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.
HOPE IT WORKS
Posted: Thu Feb 28, 2008 10:42 am
by WingletE
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!
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;
}
}
}
}
Posted: Mon Mar 03, 2008 2:46 pm
by WingletE
Another question:
I've seen at somewhere that this problem can be solved using DFS, but how can I use DFS without getting TLE?
And could someone explain the ideas of other solutions for me?
I think there are many better solutions above, but I can't understand them very well.
Thanks.
Posted: Fri Mar 14, 2008 2:07 pm
by turcse143
u can solve this easily by use flowyed warshel algorithm.
but u also solve this by DFS.
--U HAVE TO CHECK THE LAST NODE OF A PATH.
--SAVE THE LENGTH OF PATH & LAST NODE.
--NODE NEED RUN BY ALL THE NODE.
--START WITH SOURCE NODE.
ALL THE BEST
Re: 10000 - Longest Path
Posted: Mon May 12, 2008 8:32 am
by hammerx
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
Posted: Thu Aug 07, 2008 3:00 am
by MarioYC
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;
}
Re: 10000 - Longest Path(15 time WA)
Posted: Fri Sep 12, 2008 10:25 pm
by kbr_iut
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.
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;
}
Re: 10000 - Longest Path
Posted: Wed Dec 24, 2008 1:01 am
by ashish_thakur
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++;
}
}
Re: 10000 - Longest Path
Posted: Wed Dec 24, 2008 1:50 am
by mf
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.
Re: 10000 - Longest Path
Posted: Wed Dec 24, 2008 11:30 am
by ashish_thakur
Thanks , Now I am getting TL error is there any standard algo for this type of problem
Re: 10000 - Longest Path
Posted: Wed Dec 24, 2008 11:49 am
by Articuno
You can use BFS to find the longest path. I used that and got AC.