10000 - Longest Paths
Moderator: Board moderators
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10000 - Longest Path
try using the Floyd Warshall algorithm.
Check input and AC output for thousands of problems on uDebug!
why runtime error is occuring for my code..uva-10000
Code: Select all
#include<stdio.h>
typedef struct listing{
int length,finishing_point,index;
};
int main()
{int cases[100][3];
int start,total_node,n;
n=0;
do{
scanf("%d",&total_node);
if(total_node==0)break;
scanf("%d",&start);
int a[100][total_node];
int p,q,i;
i=0;
do
{scanf("%d %d",&p,&q);
a[i][0]=p;
a[i][1]=q;
i++;
}
while(p!=0||q!=0);
int j=i,k,l,m;
listing found[j-1];
m=0;
for(i=0;i<j-1;i++)
{if(start==a[i][0])
{k=1;
for(l=0;l<j-1;l++)
{
if(a[i][k]==a[l][0])
{ a[i][k+1]=a[l][1];
k++;
}
if(k==total_node-1)break;
}
found[m].index=i;
found[m].length=k;
found[m].finishing_point=a[i][k];
m++;
}
}
int max_length=found[0].length,selected;
for(i=0;i<m;i++)
{if(found[i].length>max_length)
{max_length=found[i].length;
selected=i;
}
else if(found[i].length==max_length)
{
for(j=1;j<max_length;j++)
{if(a[found[selected].index][j]<a[found[i].index][j])
break;
else if(a[found[i].index][j]<a[found[selected].index][j])
{selected=i;break;
}
}
}
}
if(m!=1)
{
cases[n][0]=start;
cases[n][1]=found[selected].length;
cases[n][2]=found[selected].finishing_point;
}
else{
cases[n][0]=start;
cases[n][1]=found[0].length;
cases[n][2]=found[0].finishing_point;
}
n++;
}
while(total_node!=0);
int i;
for(i=0;i<n;i++)
printf("Case %d: The longest path from %d has length %d , finishing at %d.\n",i+1,cases[i][0],cases[i][1],cases[i][2]);
return 0;
}
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: why runtime error is occuring for my code..uva-10000
Print a new line after each test case. You're also printing an extra space after the length.
Check input and AC output for thousands of problems on uDebug!
-
- New poster
- Posts: 15
- Joined: Fri May 30, 2014 12:09 am
Re: 10000 - Longest Paths
I solved this in 0.065s using BFS in C. Consider this test case...
ACC output is:
The problem people are having with BFS is most likely due to not revisiting nodes. Although in a BFS you don't visit a node that has already been visited, in this problem it is possible to visit a node later on... when the path is longer! Use the test case above and let your BFS algorithm re-visit visited nodes if and only if a larger path was found. And with BFS you don't waste any time on the components that are not connected to the start vertex, like you would using Floyd-Warshall. And another thing, on this problem you WILL get WA if you do not put 2 newlines on every output line. I know some problems you cannot have any newlines at the end but you definitely need them for this one.
Code: Select all
4
1
1 3
1 2
2 3
1 2
0 0
0
Code: Select all
Case 1: The longest path from 1 has length 3, finishing at 2.
Re: 10000 - Longest Paths. Getting WA everytime!!!
why WA?? can anyone see my code and give some advise???
thanks in advance
Code: Select all
#include<iostream>
#include<vector>
#define MAX 101
using namespace std;
vector<vector<int> >g(MAX);
int dis[MAX];
void DFS_VISIT(int c,int visited[]) {
int v;
for(int i=0;i<g[c].size();i++) {
v=g[c][i];
dis[v]=dis[c]+1;
if(visited[v]==0){
visited[v]=1;
DFS_VISIT(v,visited);
}
}
}
int DFS(int s,int n) {
int v,maximum=0,finalPoint,visited[101];
for(int i=0;i<101;i++) {
dis[i]=0;
visited[i]=0;
}
if(g[s].size()==0) return s;
for(int i=0;i<g[s].size();i++) {
v=g[s][i];
dis[v]=1;
visited[v]=1;
DFS_VISIT(v,visited);
}
for(int i=1;i<=n;i++) {
if(maximum<dis[i]) {
maximum=dis[i];
finalPoint=i;
}
}
return finalPoint;
}
int main()
{
int num_vertex,start,x,y,t=1,p;
while(1) {
cin>>num_vertex;
if(num_vertex==0) break;
cin>>start;
for(int i=0;i<101;i++) g[i].clear();
while(1) {
cin>>x>>y;
if(x==0 && y==0) break;
g[x].push_back(y);
}
p=DFS(start,num_vertex);
cout<<"Case "<<t<<": The longest path from "<<start<<" has length "<<dis[p]<<", finishing at "<<p<<"."<<endl<<endl;
t++;
}
return 0;
}
Last edited by LazyTym on Mon Sep 29, 2014 8:18 am, edited 1 time in total.
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10000 - Longest Paths
Don't read from a file.
Check input and AC output for thousands of problems on uDebug!
Re: 10000 - Longest Paths
i do not read from a file now bt still i am getting WA...........check my code pls...i cann't find bug in my code........brianfry713 wrote:Don't read from a file.
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10000 - Longest Paths
Input:AC output:
Code: Select all
17
1
1 7
1 9
1 12
1 13
1 14
1 15
2 3
2 4
2 5
2 7
2 9
2 11
2 12
2 14
2 15
2 17
3 4
3 6
3 8
3 9
3 12
3 16
3 17
4 5
4 6
4 9
4 11
4 12
4 14
4 15
4 16
5 11
5 12
6 7
6 12
6 13
6 14
6 16
7 13
7 16
8 10
8 12
8 13
8 15
8 16
9 11
9 12
9 14
9 15
10 13
10 14
10 16
10 17
11 12
11 13
11 15
11 16
11 17
12 13
12 15
12 17
13 16
13 17
14 15
14 16
15 17
16 17
0 0
7
1
1 2
1 3
1 4
1 5
2 5
2 6
2 7
3 4
3 6
3 7
4 5
4 6
5 6
0 0
7
1
1 2
1 3
1 4
1 7
2 4
2 6
2 7
3 4
3 5
3 6
4 5
4 6
4 7
5 7
6 7
0 0
19
1
1 4
1 5
1 7
1 8
1 10
1 11
1 12
1 14
1 15
1 16
1 17
1 18
1 19
2 3
2 7
2 9
2 10
2 12
2 14
2 15
2 17
2 19
3 4
3 5
3 7
3 9
3 12
3 14
3 16
3 18
3 19
4 5
4 6
4 8
4 10
4 11
4 12
4 13
4 16
4 17
4 18
5 8
5 9
5 10
5 13
5 14
5 16
5 18
5 19
6 7
6 10
6 13
6 15
6 16
6 17
6 19
7 8
7 9
7 11
7 13
7 15
7 17
7 18
7 19
8 10
8 18
8 19
9 12
9 14
9 17
9 18
9 19
10 11
10 12
10 13
10 15
10 16
11 13
11 16
11 19
12 13
12 14
12 17
12 18
12 19
13 14
13 16
13 17
13 18
13 19
14 15
14 16
14 19
15 16
15 17
16 19
0 0
9
1
1 2
1 4
1 7
1 8
1 9
2 4
2 8
2 9
3 4
3 6
4 5
4 8
5 6
5 7
6 8
7 8
7 9
0 0
5
1
1 2
1 4
2 4
3 4
0 0
17
1
1 2
1 6
1 9
2 4
2 6
2 13
2 16
3 5
3 11
4 9
4 10
4 12
4 14
5 8
5 16
6 8
6 13
6 15
6 16
6 17
7 9
7 10
7 13
7 16
7 17
8 9
8 10
8 11
8 12
8 13
8 16
8 17
9 11
9 14
10 11
10 12
10 13
10 16
10 17
11 13
11 15
11 17
12 14
12 16
12 17
13 14
13 15
13 16
14 16
14 17
15 16
15 17
16 17
0 0
17
1
1 2
1 3
1 5
1 6
1 7
1 8
1 11
1 12
1 13
1 15
2 3
2 4
2 8
2 9
2 10
2 14
2 15
2 16
3 5
3 6
3 7
3 14
3 15
3 17
4 6
4 8
4 9
4 11
4 13
4 16
4 17
5 6
5 11
5 12
5 14
5 15
5 17
6 7
6 9
6 10
6 11
6 13
6 17
7 9
7 10
7 11
7 15
7 16
8 9
8 10
8 12
8 16
8 17
9 11
9 12
9 13
9 16
9 17
10 12
10 13
10 14
10 15
10 17
11 14
11 16
12 14
13 15
14 17
15 16
15 17
16 17
0 0
11
1
1 5
1 6
1 9
1 10
2 6
2 11
3 5
3 7
3 8
3 10
4 5
4 6
4 7
4 8
4 9
4 10
5 6
5 9
5 10
5 11
6 8
6 9
6 11
7 8
7 9
7 10
8 11
9 11
0 0
13
1
1 4
1 5
1 6
1 7
1 8
1 10
1 13
2 3
2 4
2 6
2 7
2 8
2 12
2 13
3 5
3 6
3 7
3 8
3 10
3 11
3 12
3 13
4 8
4 9
4 12
5 6
5 7
5 9
5 11
6 7
6 8
6 9
6 11
7 8
7 9
7 13
8 10
9 10
9 11
9 12
9 13
10 11
11 12
0 0
7
1
1 3
1 4
1 5
2 3
2 4
3 6
5 6
6 7
0 0
20
1
1 2
1 4
1 7
1 9
1 10
1 13
1 16
1 17
1 18
1 19
1 20
2 4
2 5
2 6
2 7
2 9
2 10
2 11
2 12
2 13
2 14
2 15
2 16
2 18
2 20
3 4
3 5
3 6
3 7
3 8
3 10
3 11
3 12
3 14
3 16
3 17
3 18
3 19
4 5
4 6
4 7
4 11
4 12
4 13
4 14
4 15
4 17
4 18
4 19
5 7
5 8
5 12
5 13
5 14
5 15
5 19
6 7
6 9
6 13
6 14
6 15
6 17
6 19
7 8
7 9
7 14
7 15
7 16
8 9
8 12
8 15
8 17
8 18
8 19
9 12
9 14
9 15
9 17
9 18
9 20
10 11
10 12
10 15
10 16
10 20
11 13
11 14
11 17
11 18
11 19
12 16
12 19
13 14
13 16
13 20
14 18
15 18
15 19
16 20
17 20
18 19
18 20
0 0
14
1
1 5
1 6
1 8
1 10
1 11
1 13
2 4
2 7
2 8
2 10
2 11
3 6
3 13
4 11
4 14
5 6
5 11
5 13
5 14
6 8
6 9
6 10
6 11
6 12
6 13
7 9
7 10
7 12
8 9
8 12
9 11
10 12
10 14
11 14
12 14
0 0
19
1
1 4
1 5
1 7
1 10
1 13
1 14
1 16
1 17
1 19
2 3
2 8
2 13
2 14
2 16
2 17
2 18
3 4
3 5
3 7
3 10
3 12
3 14
3 17
3 18
4 5
4 6
4 11
4 13
4 17
5 6
5 7
5 10
5 11
5 13
5 16
5 17
6 9
6 12
6 17
6 19
7 8
7 10
7 11
7 12
7 14
7 15
7 16
7 18
7 19
8 9
8 10
8 13
8 16
8 17
8 19
9 12
9 13
9 14
9 16
9 18
9 19
10 11
10 14
10 19
11 12
11 13
11 14
11 15
11 16
11 18
12 16
12 17
12 18
12 19
13 16
13 17
13 19
14 15
14 16
14 17
14 18
15 16
15 17
16 17
16 19
17 19
18 19
0 0
18
1
1 2
1 3
1 5
1 6
1 10
1 16
1 17
1 18
2 3
2 5
2 10
2 13
2 14
2 15
2 16
3 6
3 10
3 11
3 13
3 14
3 15
3 16
4 11
4 12
4 14
4 16
5 10
5 13
5 14
5 15
6 7
6 8
6 10
6 11
6 12
6 13
6 15
6 16
6 17
6 18
7 8
7 10
7 11
7 13
7 14
7 16
7 17
7 18
8 9
8 10
8 11
8 13
8 14
8 15
8 16
9 11
9 13
9 14
9 18
10 11
10 13
10 14
10 15
10 16
11 12
11 14
11 16
11 18
12 14
12 16
12 17
13 14
13 15
13 17
14 15
14 16
14 18
15 18
16 17
16 18
0 0
5
1
1 2
1 4
1 5
2 3
2 5
3 5
4 5
0 0
5
1
2 3
2 4
3 4
3 5
4 5
0 0
6
1
1 3
1 4
2 4
2 5
2 6
3 5
4 6
0 0
4
1
1 2
0 0
11
1
1 3
1 5
1 9
1 11
2 7
2 8
2 9
2 10
3 5
3 6
4 5
4 9
5 10
6 8
7 8
7 9
7 10
7 11
8 9
8 10
9 10
10 11
0 0
19
1
1 3
1 5
1 10
1 13
1 18
2 4
2 6
2 7
2 8
2 9
2 11
2 15
2 16
3 8
3 11
3 14
3 15
3 17
3 18
3 19
4 5
4 6
4 10
4 13
4 15
4 18
5 10
5 12
5 14
5 15
5 16
5 18
5 19
6 7
6 8
6 11
6 12
6 15
6 18
7 10
7 11
7 13
7 14
7 15
7 16
7 19
8 9
8 10
8 11
8 12
8 13
8 18
8 19
9 10
9 11
10 11
10 12
10 14
10 15
10 16
10 18
10 19
11 12
11 14
11 16
11 19
12 14
12 16
12 19
13 14
13 16
13 17
14 15
14 16
14 17
14 18
15 17
15 19
16 19
17 18
0 0
5
1
1 2
1 4
2 4
4 5
0 0
15
1
1 6
1 8
1 9
1 13
1 14
2 3
2 4
2 6
2 7
2 8
2 10
2 11
2 15
3 7
3 9
3 10
3 13
3 15
4 7
4 8
4 9
4 14
5 6
5 8
5 11
5 13
5 15
6 8
6 9
6 10
6 13
7 8
7 12
7 13
7 15
8 15
9 11
9 12
9 13
9 15
10 14
10 15
11 13
11 14
12 13
13 14
14 15
0 0
11
1
1 2
1 4
1 5
1 6
1 7
1 8
1 9
2 4
2 5
2 6
2 8
2 9
3 4
3 5
3 8
3 9
4 5
4 7
4 9
4 11
5 6
5 7
6 8
6 10
7 10
7 11
8 9
9 10
10 11
0 0
4
1
1 3
1 4
2 3
2 4
3 4
0 0
11
1
1 2
1 4
1 9
1 11
2 3
2 5
2 6
2 8
2 10
2 11
3 8
3 10
4 5
4 9
4 11
5 6
5 7
5 8
6 7
6 8
6 10
7 10
8 9
8 10
9 10
9 11
10 11
0 0
20
1
1 2
1 4
1 5
1 7
1 8
1 10
1 12
1 15
1 20
2 3
2 4
2 5
2 7
2 9
2 10
2 12
2 13
2 16
2 17
2 18
2 19
2 20
3 5
3 7
3 8
3 10
3 12
3 13
3 14
3 15
3 19
4 5
4 7
4 8
4 14
4 15
4 20
5 7
5 9
5 10
5 11
5 15
5 16
6 7
6 9
6 16
6 19
7 8
7 9
7 10
7 12
7 14
7 19
7 20
8 10
8 11
8 13
8 16
8 20
9 11
9 12
9 13
9 14
9 15
9 20
10 18
10 19
10 20
11 13
11 16
11 18
11 19
12 15
12 16
12 17
12 20
13 15
13 16
13 18
13 19
14 16
14 20
15 16
15 17
15 18
15 20
18 19
18 20
19 20
0 0
15
1
1 5
1 6
1 9
1 13
1 15
2 6
2 8
3 4
3 6
3 7
3 9
3 11
3 14
3 15
4 5
4 10
4 13
5 12
5 15
6 7
6 8
6 9
6 11
6 15
7 9
7 10
7 12
7 14
7 15
8 11
8 12
8 14
8 15
9 10
9 11
9 14
10 11
10 13
11 12
11 14
11 15
12 13
12 14
13 14
13 15
14 15
0 0
20
1
1 4
1 9
1 11
1 12
1 14
1 18
1 19
2 3
2 7
2 9
2 10
2 11
2 16
2 17
2 19
3 4
3 8
3 14
3 15
3 16
3 19
3 20
4 5
4 6
4 8
4 10
4 11
4 13
4 17
4 19
5 7
5 8
5 10
5 11
5 15
5 16
5 17
5 18
6 7
6 12
6 13
6 14
6 15
6 17
6 18
6 19
6 20
7 9
7 10
7 11
7 12
7 13
7 14
7 16
7 17
7 18
8 13
8 16
8 17
9 10
9 12
9 17
9 18
9 19
10 13
10 14
10 15
10 17
10 18
10 20
11 17
11 18
12 13
12 14
12 17
12 20
13 15
13 16
13 18
13 19
13 20
14 16
14 17
14 20
15 16
15 18
15 20
16 18
17 18
19 20
0 0
5
1
1 2
1 3
2 4
3 4
0 0
20
1
1 4
1 5
1 7
1 8
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
2 3
2 7
2 9
2 10
2 11
2 12
2 13
2 15
2 17
2 18
3 6
3 7
3 8
3 12
3 14
3 16
3 17
3 18
3 19
3 20
4 6
4 8
4 10
4 13
4 15
5 6
5 7
5 9
5 10
5 13
5 17
5 18
5 19
6 7
6 11
6 12
6 13
6 14
6 16
6 17
6 20
7 11
7 13
7 14
7 15
7 16
7 18
7 19
7 20
8 10
8 14
8 16
8 18
8 20
9 11
9 14
9 15
9 16
9 18
10 12
10 13
10 14
10 17
10 18
11 12
11 17
11 20
12 15
12 20
13 15
13 17
13 19
14 15
14 16
14 17
14 20
15 19
16 19
17 19
18 19
18 20
19 20
0 0
18
1
1 2
1 5
1 7
1 8
1 10
1 12
1 14
1 17
2 7
2 8
2 9
2 10
2 12
2 16
2 17
2 18
3 4
3 6
3 8
3 9
3 12
3 14
3 15
3 18
4 6
4 7
4 8
4 10
4 12
4 13
4 14
4 15
4 16
5 6
5 7
5 9
5 12
5 15
5 16
5 17
6 8
6 10
6 12
6 14
6 15
6 16
6 17
7 8
7 10
7 14
7 15
7 17
8 12
8 13
8 14
8 16
8 17
8 18
9 10
9 12
9 13
9 18
10 11
10 12
10 15
10 18
11 16
12 14
12 15
13 14
13 15
13 17
14 16
14 17
15 16
15 18
16 17
17 18
0 0
7
1
1 2
1 4
1 5
1 7
2 5
2 7
3 6
5 6
5 7
6 7
0 0
8
1
1 3
1 4
1 6
2 5
2 7
2 8
3 5
3 6
4 6
4 7
5 7
7 8
0 0
5
1
1 2
1 4
2 3
2 4
2 5
4 5
0 0
9
1
1 2
1 3
1 4
1 6
1 9
2 3
2 9
3 4
3 5
3 6
4 7
4 9
5 8
6 8
6 9
7 8
7 9
8 9
0 0
9
1
1 2
1 4
1 5
1 6
1 7
1 9
2 4
2 7
2 8
3 5
3 6
4 9
5 6
5 7
6 7
6 9
7 9
0 0
8
1
1 2
1 3
2 3
4 6
4 7
4 8
5 8
6 8
7 8
0 0
6
1
1 2
1 3
1 4
1 6
2 3
2 5
2 6
3 4
3 5
3 6
4 5
4 6
5 6
0 0
20
1
1 2
1 3
1 5
1 6
1 8
1 9
1 11
1 15
1 16
1 17
1 20
2 3
2 7
2 8
2 10
2 11
2 12
2 14
2 15
2 17
2 19
2 20
3 4
3 6
3 9
3 12
3 13
3 15
3 16
3 18
3 19
4 5
4 9
4 13
4 16
4 18
4 19
5 6
5 7
5 8
5 11
5 12
5 13
5 14
5 15
5 17
5 19
6 7
6 10
6 11
6 15
6 18
6 20
7 9
7 11
7 13
7 14
7 15
7 17
7 19
7 20
8 11
8 13
8 14
8 16
8 18
8 19
9 11
9 13
9 16
9 17
9 19
9 20
10 11
10 15
10 17
10 18
10 20
11 14
11 15
11 16
11 18
11 20
12 20
13 14
13 15
13 19
14 17
14 19
14 20
15 16
15 17
16 17
16 20
17 18
17 20
19 20
0 0
15
1
1 2
1 3
1 6
1 10
1 11
1 12
1 14
2 3
2 6
2 7
2 10
2 12
2 13
2 15
3 4
3 5
3 7
3 9
3 10
3 12
3 15
4 5
4 6
4 8
4 10
4 12
4 13
5 6
5 8
5 13
5 14
5 15
6 7
6 8
6 9
6 10
6 12
7 8
7 9
7 10
7 14
7 15
8 9
8 11
8 12
8 13
8 14
9 10
9 11
9 12
10 11
10 13
10 14
10 15
11 14
0 0
16
1
1 2
1 3
1 4
1 5
1 8
1 12
1 13
2 5
2 6
2 7
2 8
2 9
2 16
3 8
3 11
3 12
3 14
3 15
4 5
4 8
4 12
4 13
4 16
5 8
5 14
5 16
6 7
6 8
6 11
6 13
6 14
6 15
6 16
7 8
7 10
7 11
7 16
8 9
8 11
8 12
8 15
8 16
9 12
9 14
10 11
10 14
10 15
10 16
11 13
11 14
12 15
13 14
13 16
14 15
14 16
15 16
0 0
7
1
1 2
1 4
1 5
1 7
2 3
3 5
4 6
4 7
5 7
6 7
0 0
2
1
0 0
10
1
1 3
1 4
1 5
1 9
1 10
2 3
2 4
2 5
2 6
2 8
2 9
3 5
3 8
3 10
4 5
4 10
5 9
5 10
6 9
7 8
7 9
7 10
9 10
0 0
5
1
1 2
1 3
1 4
2 3
2 4
3 4
4 5
0 0
6
1
1 2
1 3
2 5
3 5
3 6
0 0
11
1
1 6
1 8
1 10
1 11
2 4
2 5
2 6
3 5
3 8
3 9
3 10
4 5
4 7
4 8
4 10
4 11
5 7
5 8
5 10
5 11
6 7
6 8
7 9
7 11
8 9
8 10
9 11
10 11
0 0
14
1
1 3
1 7
1 8
1 10
1 11
1 12
1 14
2 4
2 6
2 7
2 8
2 9
2 12
2 13
2 14
3 5
3 6
3 7
3 11
3 12
4 6
4 8
4 9
4 10
4 13
4 14
5 6
5 8
5 10
5 11
6 7
6 8
6 9
6 10
6 12
6 13
7 10
7 12
8 10
8 11
9 11
9 13
9 14
10 11
10 13
11 14
12 13
12 14
13 14
0 0
5
1
1 2
1 5
2 3
2 4
3 4
3 5
4 5
0 0
3
1
1 2
1 3
2 3
0 0
16
1
1 2
1 6
1 7
1 10
1 14
2 3
2 4
2 8
2 9
2 10
2 14
2 15
2 16
3 5
3 6
3 8
3 9
3 10
3 13
4 9
4 10
4 12
4 13
4 14
5 7
5 9
5 13
5 14
6 9
6 11
6 12
6 13
6 14
6 15
6 16
7 8
8 11
8 12
8 13
8 15
8 16
9 10
9 16
10 11
10 12
10 15
10 16
11 12
11 14
11 15
11 16
12 14
12 15
13 15
14 15
15 16
0 0
17
1
1 2
1 3
1 4
1 5
1 6
1 7
1 9
1 11
1 14
1 15
1 16
2 4
2 5
2 6
2 7
2 8
2 10
2 11
2 12
2 13
3 4
3 5
3 6
3 7
3 10
3 11
3 16
3 17
4 5
4 6
4 7
4 11
4 12
4 17
5 6
5 9
5 10
5 11
5 16
5 17
6 8
6 9
6 12
6 13
6 14
7 8
7 9
7 10
7 11
7 14
7 15
7 16
7 17
8 9
8 11
8 12
8 14
8 15
8 17
9 15
9 16
9 17
10 12
10 13
10 16
11 13
11 15
11 17
12 13
12 15
12 17
13 14
13 15
13 17
14 17
15 16
16 17
0 0
4
1
1 2
2 3
3 4
0 0
11
1
1 2
1 3
1 4
1 6
1 7
2 3
2 5
2 7
2 8
2 9
3 5
3 7
3 8
3 10
3 11
4 5
4 6
4 10
5 8
5 9
5 11
6 7
6 8
6 9
6 10
6 11
8 11
9 10
9 11
0 0
2
1
1 2
0 0
10
1
1 6
1 9
2 3
2 5
2 9
2 10
3 6
3 10
4 6
4 10
5 9
6 7
6 8
6 9
7 8
7 10
8 10
9 10
0 0
19
1
1 4
1 6
1 7
1 8
1 9
1 11
1 13
1 14
2 3
2 4
2 5
2 9
2 11
2 13
2 15
3 4
3 5
3 6
3 7
3 10
3 11
3 14
3 18
3 19
4 5
4 6
4 7
4 8
4 13
4 15
4 16
4 18
5 7
5 8
5 9
5 10
5 16
5 18
5 19
6 7
6 9
6 15
6 16
6 17
6 18
7 8
7 11
7 13
7 15
7 18
8 11
8 13
8 14
8 15
8 16
8 18
8 19
9 12
9 13
9 14
9 15
9 16
9 17
9 19
10 11
10 12
10 13
10 15
10 19
11 14
11 16
11 18
12 14
12 16
12 17
12 19
13 14
13 15
14 15
14 17
15 18
16 17
16 18
16 19
17 18
17 19
0 0
20
1
1 4
1 5
1 7
1 8
1 12
1 17
1 19
1 20
2 4
2 5
2 6
2 9
2 10
2 11
2 13
2 14
2 15
2 16
2 20
3 4
3 6
3 7
3 9
3 10
3 12
3 16
4 6
4 7
4 8
4 10
4 12
4 14
4 16
4 17
4 18
5 6
5 10
5 16
6 8
6 9
6 10
6 11
6 12
6 13
6 14
6 15
6 16
6 17
7 8
7 10
7 11
8 9
8 10
8 12
8 13
8 14
8 15
8 16
8 20
9 10
9 11
9 15
9 16
9 20
10 13
10 15
10 17
10 18
10 19
11 12
11 14
11 16
11 19
11 20
12 14
12 17
12 19
13 14
13 20
14 15
14 16
14 17
15 17
15 18
15 19
15 20
17 18
17 20
18 19
0 0
10
1
1 4
1 7
2 3
2 6
2 9
3 4
3 5
3 6
3 8
3 9
4 6
4 7
4 8
4 10
5 6
5 8
6 7
6 8
6 10
7 10
8 10
0 0
15
1
1 2
1 6
1 8
1 9
1 11
1 13
2 6
2 11
2 12
2 14
2 15
3 6
3 8
3 9
3 11
3 15
4 6
4 8
4 11
4 13
5 6
5 12
5 13
6 8
6 9
6 10
6 11
6 12
6 13
6 15
7 8
7 10
7 11
7 13
7 14
7 15
8 9
8 12
9 14
9 15
10 12
10 14
11 12
11 15
12 14
13 14
0 0
16
1
1 2
1 3
1 4
1 6
1 13
2 4
2 8
2 11
2 13
2 14
2 15
2 16
3 4
3 5
3 11
3 14
3 15
4 6
5 6
5 7
5 8
5 12
5 15
6 7
6 8
6 9
6 10
6 11
6 12
6 15
8 10
8 11
8 12
8 13
8 15
9 14
9 15
10 12
10 13
10 14
10 15
11 12
11 13
11 15
12 13
12 14
12 16
13 14
13 15
13 16
14 15
0 0
10
1
1 3
1 4
1 6
1 7
1 8
1 10
2 3
2 4
2 8
2 9
3 4
3 8
4 5
4 6
4 7
4 10
5 6
6 7
6 8
6 9
7 8
7 10
8 9
8 10
0 0
3
1
0 0
11
1
1 7
1 9
1 10
2 3
2 6
2 9
2 11
3 4
3 5
3 6
3 11
4 5
4 7
4 10
5 6
5 9
5 10
5 11
6 7
6 10
7 9
7 10
8 11
9 10
0 0
5
1
1 2
1 3
1 4
1 5
2 4
3 4
3 5
4 5
0 0
13
1
1 2
1 4
1 5
1 6
1 7
1 8
1 10
1 11
1 12
2 4
2 6
2 8
2 9
2 13
3 4
3 7
3 11
3 12
4 7
4 9
4 10
4 11
4 12
5 7
5 8
5 12
6 8
6 11
6 12
7 9
7 11
8 9
8 10
8 12
8 13
9 13
10 11
11 13
0 0
15
1
1 4
1 6
1 7
1 8
1 10
1 11
1 12
1 15
2 7
2 8
2 10
2 12
2 15
3 4
3 5
3 7
3 12
3 13
3 14
3 15
4 5
4 8
4 9
4 11
4 12
4 14
5 8
5 10
5 13
5 14
6 7
6 10
6 11
6 13
6 15
7 9
7 10
7 11
7 14
7 15
8 9
8 10
8 11
8 12
8 13
8 14
8 15
9 10
9 12
9 14
11 12
11 14
12 13
12 14
12 15
0 0
10
1
1 2
1 3
1 5
1 9
1 10
2 7
3 9
4 5
4 7
4 8
4 9
4 10
5 8
5 9
5 10
6 7
6 8
6 10
7 10
0 0
12
1
1 9
1 11
2 5
2 6
2 7
2 8
2 11
3 4
3 5
3 6
3 7
3 8
3 10
3 11
4 5
4 6
4 7
4 8
4 9
4 10
4 12
5 6
5 9
6 8
6 9
6 11
7 10
7 11
7 12
8 10
8 12
9 11
10 11
10 12
11 12
0 0
11
1
1 2
1 4
1 5
1 9
2 8
4 5
4 6
4 8
4 11
5 6
5 7
5 8
5 9
6 7
7 9
7 10
8 9
8 10
8 11
9 10
9 11
10 11
0 0
9
1
1 2
1 3
1 6
2 3
2 5
2 7
2 8
3 4
3 5
3 7
3 9
4 6
4 7
4 8
5 7
5 8
5 9
6 8
6 9
7 8
7 9
0 0
2
1
0 0
15
1
1 4
1 6
1 8
1 11
1 12
1 15
2 3
2 5
2 6
2 12
2 13
2 14
2 15
3 4
3 6
3 9
3 10
3 11
3 15
4 6
4 11
4 13
5 6
5 9
5 11
5 12
5 13
5 14
5 15
6 8
6 10
6 12
6 13
6 15
7 11
7 14
7 15
8 11
8 12
8 13
8 15
9 12
9 13
9 14
10 11
10 12
10 13
10 14
11 12
11 14
12 13
13 14
13 15
14 15
0 0
20
1
1 7
1 8
1 10
1 11
1 14
1 15
1 19
1 20
2 5
2 6
2 9
2 10
2 11
2 14
2 20
3 4
3 7
3 11
3 14
3 15
3 16
3 17
3 20
4 8
4 9
4 10
4 11
4 12
4 13
4 15
4 19
4 20
5 6
5 8
5 9
5 11
5 15
5 16
5 18
5 19
5 20
6 8
6 9
6 10
6 11
6 13
6 16
6 17
6 19
6 20
7 8
7 15
7 17
7 18
7 19
8 9
8 10
8 13
8 14
8 19
9 12
9 15
9 18
10 11
10 13
10 14
10 15
10 16
10 17
11 13
11 14
11 15
11 16
11 17
11 19
11 20
12 15
12 18
12 19
13 19
14 15
14 17
14 20
15 19
16 17
16 18
16 20
17 20
18 19
19 20
0 0
6
1
1 2
1 4
2 3
2 5
2 6
3 4
0 0
15
1
1 2
1 5
1 7
1 8
1 9
1 10
1 11
1 15
2 3
2 4
2 5
2 7
2 10
2 11
2 12
2 13
2 14
3 4
3 7
3 8
3 10
3 14
3 15
4 5
4 7
4 10
4 11
4 15
5 8
5 10
5 12
5 13
5 14
5 15
6 7
6 15
7 11
7 15
8 10
8 11
8 13
8 14
8 15
9 10
9 11
9 12
9 13
10 14
11 13
11 15
12 13
12 15
13 14
14 15
0 0
14
1
1 5
1 8
1 9
1 10
1 14
2 3
2 6
2 8
2 9
2 10
2 12
2 14
3 5
4 6
4 8
4 9
4 11
4 12
4 13
4 14
5 6
5 8
5 10
5 13
6 8
6 9
6 11
6 12
6 14
7 10
8 9
8 11
8 13
9 10
9 12
9 13
10 12
10 14
12 13
12 14
13 14
0 0
2
1
1 2
0 0
9
1
1 2
1 5
1 7
2 3
2 4
2 7
3 5
3 7
4 7
4 8
5 8
5 9
6 7
6 9
7 9
0 0
20
1
1 2
1 12
1 14
1 19
1 20
2 4
2 5
2 6
2 7
2 8
2 9
2 11
2 12
2 18
2 19
3 4
3 5
3 7
3 8
3 10
3 11
3 13
3 14
3 18
3 19
3 20
4 7
4 8
4 9
4 11
4 12
4 15
4 16
4 17
4 18
5 6
5 8
5 9
5 10
5 18
5 19
5 20
6 10
6 11
6 14
6 15
6 19
7 8
7 10
7 11
7 12
7 13
7 16
7 19
8 11
8 12
8 14
8 16
8 17
9 10
9 16
9 20
10 11
10 13
10 16
10 17
10 19
10 20
11 12
11 13
11 15
11 16
11 17
11 19
11 20
12 14
12 17
12 19
13 15
13 17
13 20
14 18
15 17
15 18
16 20
17 18
18 19
18 20
19 20
0 0
6
1
1 3
1 4
1 5
1 6
2 3
2 4
2 5
3 4
3 5
4 6
0 0
6
1
1 2
1 3
1 4
1 5
1 6
2 3
2 5
3 5
4 5
4 6
5 6
0 0
20
1
1 3
1 7
1 8
1 11
1 15
1 16
1 17
1 20
2 4
2 5
2 6
2 7
2 8
2 10
2 11
2 12
2 13
2 17
3 4
3 6
3 9
3 10
3 11
3 16
3 18
3 20
4 5
4 7
4 9
4 10
4 11
4 12
4 13
4 14
4 16
4 17
4 18
4 20
5 7
5 9
5 11
5 14
5 17
6 7
6 10
6 11
6 12
6 13
6 14
6 17
6 18
7 8
7 9
7 12
7 15
7 17
7 20
8 11
8 13
8 16
8 17
8 18
9 10
9 18
9 20
10 11
10 12
10 14
10 16
10 17
10 18
10 19
11 13
11 14
11 19
12 14
12 15
12 17
12 18
12 19
12 20
13 14
13 17
13 18
13 19
13 20
14 16
14 18
14 20
15 16
15 18
15 19
15 20
16 17
16 18
16 19
17 19
17 20
18 19
19 20
0 0
4
1
1 2
2 3
3 4
0 0
13
1
1 2
1 6
1 7
1 10
1 11
1 12
2 5
2 6
2 7
2 8
2 13
3 4
3 5
3 7
4 7
4 9
4 11
4 13
5 6
5 10
5 11
5 13
6 7
6 10
6 11
6 12
6 13
7 10
7 13
8 9
8 10
8 13
9 10
9 13
10 12
10 13
11 13
0 0
12
1
1 2
1 3
1 6
1 7
1 8
1 9
1 12
2 5
2 6
2 7
2 9
2 11
3 5
3 6
4 5
4 6
4 9
4 10
4 11
4 12
5 8
5 9
5 11
5 12
6 7
6 8
6 9
6 10
6 11
6 12
7 8
7 9
7 11
8 9
8 10
8 12
0 0
10
1
1 2
1 3
1 5
1 7
1 8
1 9
2 3
2 7
2 8
2 9
2 10
3 4
3 6
3 9
3 10
4 6
4 9
5 6
5 7
5 8
5 9
6 7
6 8
7 8
7 9
7 10
8 9
8 10
0 0
12
1
1 3
1 5
1 8
1 11
1 12
2 4
2 5
2 9
3 4
3 8
3 9
4 6
4 7
4 11
4 12
5 7
5 9
5 10
5 11
6 7
6 8
6 11
6 12
7 10
7 12
8 9
8 11
8 12
9 11
10 11
0 0
11
1
1 2
1 3
1 4
1 6
1 7
1 8
1 10
2 6
2 7
3 4
3 5
3 8
3 10
3 11
4 6
4 8
4 10
4 11
5 7
5 9
5 10
5 11
6 7
6 8
6 9
6 10
6 11
7 9
7 10
7 11
10 11
0 0
6
1
1 2
1 3
1 4
1 5
1 6
2 4
2 6
3 5
3 6
4 5
4 6
5 6
0 0
4
1
2 3
2 4
0 0
8
1
2 3
2 5
2 7
3 4
4 8
5 6
5 7
5 8
6 7
6 8
7 8
0 0
10
1
1 2
1 3
1 5
1 7
1 10
2 3
2 7
2 9
3 5
3 8
3 10
4 6
4 7
4 9
5 8
5 9
6 7
7 8
7 9
8 9
8 10
0 0
8
1
1 4
1 8
2 3
2 4
3 4
4 5
4 7
4 8
5 7
6 7
7 8
0 0
8
1
1 4
1 7
2 4
2 5
2 6
2 7
3 5
3 6
3 8
4 5
4 7
4 8
5 8
6 7
6 8
7 8
0 0
12
1
1 4
1 5
1 6
1 7
1 8
1 9
1 11
2 3
2 5
2 6
2 9
2 10
2 11
3 4
3 7
3 8
3 9
3 10
4 9
4 11
5 6
5 7
5 8
5 9
5 10
6 10
6 11
6 12
7 9
8 9
8 10
8 11
8 12
9 12
11 12
0 0
17
1
1 2
1 3
1 4
1 5
1 6
1 9
1 12
1 15
2 7
2 8
2 11
2 13
3 4
3 8
3 12
3 13
3 14
3 15
3 16
4 5
4 6
4 8
4 9
4 10
4 13
4 16
5 7
5 13
5 14
5 15
5 16
5 17
6 9
6 10
6 11
6 12
6 13
6 17
7 8
7 9
7 12
7 14
7 15
8 13
8 14
8 17
9 10
9 12
9 14
9 15
10 11
10 13
10 14
10 15
10 17
11 12
11 13
11 14
11 16
11 17
12 14
12 15
12 17
13 16
14 15
14 16
15 17
0 0
3
1
1 2
2 3
0 0
5
1
1 2
1 5
2 3
2 4
2 5
3 5
0 0
0
Code: Select all
Case 1: The longest path from 1 has length 6, finishing at 17.
Case 2: The longest path from 1 has length 4, finishing at 6.
Case 3: The longest path from 1 has length 4, finishing at 7.
Case 4: The longest path from 1 has length 11, finishing at 19.
Case 5: The longest path from 1 has length 5, finishing at 8.
Case 6: The longest path from 1 has length 2, finishing at 4.
Case 7: The longest path from 1 has length 9, finishing at 17.
Case 8: The longest path from 1 has length 10, finishing at 17.
Case 9: The longest path from 1 has length 4, finishing at 11.
Case 10: The longest path from 1 has length 7, finishing at 12.
Case 11: The longest path from 1 has length 3, finishing at 7.
Case 12: The longest path from 1 has length 9, finishing at 19.
Case 13: The longest path from 1 has length 6, finishing at 14.
Case 14: The longest path from 1 has length 11, finishing at 19.
Case 15: The longest path from 1 has length 11, finishing at 17.
Case 16: The longest path from 1 has length 3, finishing at 5.
Case 17: The longest path from 1 has length 0, finishing at 1.
Case 18: The longest path from 1 has length 2, finishing at 5.
Case 19: The longest path from 1 has length 1, finishing at 2.
Case 20: The longest path from 1 has length 6, finishing at 11.
Case 21: The longest path from 1 has length 10, finishing at 18.
Case 22: The longest path from 1 has length 3, finishing at 5.
Case 23: The longest path from 1 has length 6, finishing at 15.
Case 24: The longest path from 1 has length 8, finishing at 11.
Case 25: The longest path from 1 has length 2, finishing at 4.
Case 26: The longest path from 1 has length 7, finishing at 11.
Case 27: The longest path from 1 has length 11, finishing at 20.
Case 28: The longest path from 1 has length 9, finishing at 15.
Case 29: The longest path from 1 has length 9, finishing at 18.
Case 30: The longest path from 1 has length 2, finishing at 4.
Case 31: The longest path from 1 has length 8, finishing at 20.
Case 32: The longest path from 1 has length 8, finishing at 18.
Case 33: The longest path from 1 has length 4, finishing at 7.
Case 34: The longest path from 1 has length 4, finishing at 8.
Case 35: The longest path from 1 has length 3, finishing at 5.
Case 36: The longest path from 1 has length 6, finishing at 9.
Case 37: The longest path from 1 has length 4, finishing at 9.
Case 38: The longest path from 1 has length 2, finishing at 3.
Case 39: The longest path from 1 has length 5, finishing at 6.
Case 40: The longest path from 1 has length 12, finishing at 18.
Case 41: The longest path from 1 has length 11, finishing at 14.
Case 42: The longest path from 1 has length 9, finishing at 16.
Case 43: The longest path from 1 has length 4, finishing at 7.
Case 44: The longest path from 1 has length 0, finishing at 1.
Case 45: The longest path from 1 has length 4, finishing at 10.
Case 46: The longest path from 1 has length 4, finishing at 5.
Case 47: The longest path from 1 has length 2, finishing at 5.
Case 48: The longest path from 1 has length 4, finishing at 11.
Case 49: The longest path from 1 has length 7, finishing at 14.
Case 50: The longest path from 1 has length 4, finishing at 5.
Case 51: The longest path from 1 has length 2, finishing at 3.
Case 52: The longest path from 1 has length 10, finishing at 16.
Case 53: The longest path from 1 has length 10, finishing at 17.
Case 54: The longest path from 1 has length 3, finishing at 4.
Case 55: The longest path from 1 has length 5, finishing at 10.
Case 56: The longest path from 1 has length 1, finishing at 2.
Case 57: The longest path from 1 has length 4, finishing at 10.
Case 58: The longest path from 1 has length 8, finishing at 18.
Case 59: The longest path from 1 has length 11, finishing at 19.
Case 60: The longest path from 1 has length 4, finishing at 10.
Case 61: The longest path from 1 has length 5, finishing at 14.
Case 62: The longest path from 1 has length 9, finishing at 15.
Case 63: The longest path from 1 has length 7, finishing at 9.
Case 64: The longest path from 1 has length 0, finishing at 1.
Case 65: The longest path from 1 has length 3, finishing at 10.
Case 66: The longest path from 1 has length 3, finishing at 5.
Case 67: The longest path from 1 has length 6, finishing at 13.
Case 68: The longest path from 1 has length 6, finishing at 13.
Case 69: The longest path from 1 has length 3, finishing at 10.
Case 70: The longest path from 1 has length 3, finishing at 12.
Case 71: The longest path from 1 has length 7, finishing at 11.
Case 72: The longest path from 1 has length 5, finishing at 8.
Case 73: The longest path from 1 has length 0, finishing at 1.
Case 74: The longest path from 1 has length 8, finishing at 15.
Case 75: The longest path from 1 has length 8, finishing at 20.
Case 76: The longest path from 1 has length 3, finishing at 4.
Case 77: The longest path from 1 has length 9, finishing at 15.
Case 78: The longest path from 1 has length 8, finishing at 14.
Case 79: The longest path from 1 has length 1, finishing at 2.
Case 80: The longest path from 1 has length 4, finishing at 8.
Case 81: The longest path from 1 has length 11, finishing at 20.
Case 82: The longest path from 1 has length 3, finishing at 6.
Case 83: The longest path from 1 has length 4, finishing at 6.
Case 84: The longest path from 1 has length 13, finishing at 20.
Case 85: The longest path from 1 has length 3, finishing at 4.
Case 86: The longest path from 1 has length 6, finishing at 12.
Case 87: The longest path from 1 has length 5, finishing at 9.
Case 88: The longest path from 1 has length 7, finishing at 9.
Case 89: The longest path from 1 has length 6, finishing at 11.
Case 90: The longest path from 1 has length 6, finishing at 11.
Case 91: The longest path from 1 has length 4, finishing at 6.
Case 92: The longest path from 1 has length 0, finishing at 1.
Case 93: The longest path from 1 has length 0, finishing at 1.
Case 94: The longest path from 1 has length 5, finishing at 9.
Case 95: The longest path from 1 has length 4, finishing at 8.
Case 96: The longest path from 1 has length 3, finishing at 8.
Case 97: The longest path from 1 has length 4, finishing at 12.
Case 98: The longest path from 1 has length 11, finishing at 17.
Case 99: The longest path from 1 has length 2, finishing at 3.
Case 100: The longest path from 1 has length 3, finishing at 5.
Check input and AC output for thousands of problems on uDebug!
-
- New poster
- Posts: 2
- Joined: Thu Sep 25, 2014 2:47 pm
10000 - Longest Paths
this code works well in Eclipse , i don't know why im getting Time limit exceeded , can anyone help ???
thank you
Code: Select all
import java.util.Scanner;
import java.util.LinkedHashMap;
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
/**
*
* @author info
*/
class Main {
public static void main(String[] args) {
Main mc = new Main();
mc.begin();
}
void begin() { //LinkedHashMap<Integer,Integer> lk;
Scanner sc = new Scanner(System.in);
int[][] tab;
int pl, start, path, nextstep = 0, a, b, i, j, fin, temp;
boolean next, nextp;
int cases = 0;
pl = sc.nextInt();
while (pl != 0) {
next = true;
nextp = true;
cases++;
tab = new int[pl * pl][pl * pl];
start = sc.nextInt();
path = 0;
i = 0;
a = sc.nextInt();
b = sc.nextInt();
while (a > 0 && b > 0) {
if (i > 0) {
a = sc.nextInt();
b = sc.nextInt();
}
tab[i][0] = a;
tab[i][1] = b;
i++;
}
i = 0;
fin = 0;
temp = 0;
while (tab[i][0] != 0) {
temp = 0;
if (tab[i][0] == start) {
nextstep = tab[i][1];
next = true;
j = 0;
temp++;
while (tab[j][0] != 0) {
if (tab[j][0] == nextstep) {
nextstep = tab[j][1];
temp++;
}
j++;
}
if (path < temp) {
fin = nextstep;
path = temp;
}
}
i++;
}
System.out.println("\n Case " + cases + ": The longest path from " + start + " has length " + path + ", finishing at " + nextstep + ".");
pl = sc.nextInt();
}
}
//
}
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10000 - Longest Paths
Next time post in the existing thread.
Try using BufferedReader and BufferedWriter.
Try using BufferedReader and BufferedWriter.
Check input and AC output for thousands of problems on uDebug!
Re: 10000 - Longest Paths
Are test cases like this valid?
Shouldn't all nodes (including 4 and 3) be reachable from the starting node (1) ?
Code: Select all
4
1
1 2
4 3
3 2
0 0
0