## 10000 - Longest Paths

Moderator: Board moderators

lky
New poster
Posts: 21
Joined: Fri Dec 05, 2003 5:59 pm
Contact:

### 10000 time exceed

i use dfs to search......but time exceed.....is there a way to minimize time without rewriteing?

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
Yes there is.

First consider all the nodes that can be reached in one move.
And then nodes that can be reached in two moves - whose source is definitely nodes reachable in one move.

In this way keep increasing the length and find the answer. czar
New poster
Posts: 15
Joined: Tue Jun 10, 2003 7:30 pm
I was wondering if anyone could tell me what is wrong with my code or if I am even using the right algorithm.

I just topological sort the vertices.

[cpp]
#include<iostream>
#include<vector>
#include<cmath>
#include<queue>

using namespace std;

vector<vector<int> > g;
vector<int> indeg;
int maxl, minv;

vector<int> toposort(int start, int nv) {
int depth = -1;
int mv;
vector<int> ret(2);
queue<int> q;

q.push(start);

while(!q.empty()) {
int qs = q.size();
mv = INT_MAX;
++depth;

for(int i = 0; i < qs; i++) {
int next = q.front(); q.pop();
mv = min(mv, next);
vector<int>::iterator s = g[next].begin(), e = g[next].end();

//cout<<"NEXT: "<<next<<endl;

while(s != e) {
--indeg[*s];
if(!indeg[*s]) {
//cout<<" "<<*s<<endl;
q.push(*s);
}
++s;
}
//cout<<"DEPTH: "<<depth<<endl;
}
}
ret = depth; ret=mv;
return ret;
}

int main() {
int nv;
int start;
int i = 1;

while( cin>>nv ) {
cin.ignore();
if(nv == 0) break;

g = vector<vector<int> >(nv+1, vector<int>());
indeg = vector<int>(nv+1);
vector<int> ret;

int start;
int from, to;

cin>>start; cin.ignore();
cin>>from>>to; cin.ignore();

while(from != 0 || to != 0) {
g[from].push_back(to);
++indeg[to];
cin>>from>>to; cin.ignore();
}

ret = toposort(start, nv);
cout<<"Case "<<i<<":"<<" The longest path from "<<start<<" has length "<<ret<<", finishing at "<<ret<<".\n\n";
++i;
}
return 0;
}
[/cpp]

Sajid
Learning poster
Posts: 94
Joined: Sat Oct 05, 2002 5:34 pm
Location: CS - AIUB, Dhaka, Bangladesh.
Contact:

### Using BFS

I solved this problem using DFS long ago.
After the rejudgement, I got TLE.

Now, I used BFS to solve this problem. But its get RTE always. I increased the Queue size a lot. but still RTE. (Using Circuler Queue, I got WA).

What can I do now?
Last edited by Sajid on Sat Dec 13, 2003 12:54 pm, edited 1 time in total.
Sajid Online: www.sajidonline.com

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
You don't need a long long queue here. Just... use a BIG boolean array (of size[1..100, 1..100]) to store visited states, thus you may avoid visiting the same state more than once. Think about it.

P.S. By "state" here I mean "visiting node I with distance J".
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Sajid
Learning poster
Posts: 94
Joined: Sat Oct 05, 2002 5:34 pm
Location: CS - AIUB, Dhaka, Bangladesh.
Contact:
I did so, but now gets WA...What is the problem now? Sajid Online: www.sajidonline.com

sunhong
New poster
Posts: 19
Joined: Sat Apr 12, 2003 6:13 pm
Location: China
I got several WA on this problem.
[cpp]void solve()
{int u,v,k;
queue.clear(); queue.push_back(s);
memset(visited,0,sizeof(visited)); visited[s]=1;
memset(dist,0,sizeof(dist));
while (!queue.empty())
{u=queue.front(); queue.pop_front();
dist[v]=dist+1;
if (maxd<dist[v] || (maxd==dist[v] && t>v)) {maxd=dist[v]; t=v;}
if (!visited[v]) {visited[v]=1; queue.push_back(v);}
}
}
}
int main()
{int i,j,count;
//freopen("data.in","r",stdin);
count=0;
while (scanf("%d",&n) && n!=0)
{scanf("%d",&s);
scanf("%d %d",&i,&j);
while (!(i==0 && j==0))
scanf("%d %d",&i,&j);
}
maxd=-1; t=10010;
solve();
printf("Case %d: The longest path from %d has length %d, finishing at %

d.\n\n",++count,s,maxd,t);
}
return 1;
} [/cpp]

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
I did not check your code throughly, but you could try something yourself.
With a little time-expense, the problem can be solved using Warshall's Algorithm. I was also getting WA with BFS, then i used Warshall and got AC. You can test the output of the two programs for larger input to find if any difference occurs.

abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

### top sort (WA)

Even I use topological sorting. But I always get WA.
any thing wrong with the algo?
abi

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
I had used naive DFS the first time, but if you just keep track of "best" of each node, and only DFS when it's better, that's good enough for AC for me. (Simple pruning..)

Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm
hey per, thanks a lot man for such a quick response.

i made a really stupid mistake in my code for cycle checking. hope not too many people got misguided in this short time. next time i will consult with 1 or 2 people before making any such conclusions. and per, thanks again for such a quick response. n.b. if any of you can't understand what i'm talking about then please skip my post and may be the per's one (next) too. i made a wrong statement and he pointed it out .
Last edited by Dreamer#1 on Fri Jan 16, 2004 8:48 pm, edited 1 time in total.
Not all of our dreams can be made to come true. But still we live with the hope to turn them into reality someday.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
I got AC using topological sort. I think the trouble with the new input is not that the graphs are cyclic, but that there are nodes which are not reachable from the starting node.

It would be very interesting if you could tell me how you solved the problem without assuming that the graph is acyclic: in general, that is an NP-complete problem.

tlucz
New poster
Posts: 6
Joined: Tue Jan 27, 2004 1:41 pm
Location: Poland/Katowice
Hi! I got a WA on this problem, too. I think that my program works good. Could someone give me input and output sample??? That is my code:
[cpp]
#include <iostream>

using namespace std;

int ile_wezlow;
int poczatek;

int maks;
int tabela;
int sumy;
int konce;
int najm;

void inicjalizacja() {
int i,j;
for(i=1;i<=ile_wezlow;i++)
for(j=1;j<=ile_wezlow;j++)
tabela[j]=0;

for(i=1;i<=ile_wezlow;i++) {
sumy=-1;
konce=1;
najm=200;

}
}

void wypisz() {

cout << "Case " << przypadek << ": The longest path from " << poczatek << " has length " << maks << ", finishing at " << najm[poczatek] << "." << endl << endl;
}

int licz(int numer) {
int i,ile,m,m1;
m=0;
m1=200;

if (sumy[numer]!=-1) {
return sumy[numer];
}
else {
for(i=1;i<=ile_wezlow;i++) {
if (tabela[numer]==1) {
ile=licz(i)+1;
if (ile>=m) {

if (ile>m) {
m1=najm;
m=ile;
}
else {
if (najm<m1) { m1=najm; }
}

}
}
}

sumy[numer]=m;
najm[numer]=m1;

return m;
}
}

void oblicz() {
int i;
for(i=1;i<=ile_wezlow;i++) {
if (konce==1)
{
sumy=0;
najm[i]=i;
}
}
maks=licz(poczatek);
}

int main(void){

int x,y;

while(1) {
cin >> ile_wezlow;
if (ile_wezlow==0) goto koniec;
inicjalizacja();
cin >> poczatek;
maks=0;
while(1) {
cin >> x;
cin >> y;
if ((x==0) && (y==0)) goto oblicz;
if (x!=y) {
tabela[x][y]=1;
konce[x]=0;
}

}
oblicz:
oblicz();
wypisz();
}
koniec:

return 0;
}
[/cpp]

What's wrong with my code. Thanks a lot.[/cpp]

alu_mathics
Learning poster
Posts: 55
Joined: Sat Jan 24, 2004 9:30 pm
Location: Chittagong
Contact:
i thing bfs is sufficient for this problem.
i solved the problem using bfs.
if i visit from u 2 v,
then i considered whether d[v]>d+1.
if yes i just update it.
and finally checked which index contains the maximum distance.
thats all. Last edited by alu_mathics on Wed Jan 28, 2004 2:03 pm, edited 1 time in total.
cuii e

tlucz
New poster
Posts: 6
Joined: Tue Jan 27, 2004 1:41 pm
Location: Poland/Katowice
Thanks for the answer. But I would like somebody to test my program with input data and give me data for which my program generates wrong answer. Sorry for my english. Thanks.