10000  Longest Paths
Moderator: Board moderators
10000 time exceed
i use dfs to search......but time exceed.....is there a way to minimize time without rewriteing?
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[0] = depth; ret[1]=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[0]<<", finishing at "<<ret[1]<<".\n\n";
++i;
}
return 0;
}
[/cpp]
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[0] = depth; ret[1]=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[0]<<", finishing at "<<ret[1]<<".\n\n";
++i;
}
return 0;
}
[/cpp]

 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?
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
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".
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
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
I got several WA on this problem.
I use BFS to solve it. I don't know why. Please help me, thanks.
[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();
for (k=0;k<adj.size();k++)
{v=adj[k];
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);
for (i=0;i<=n;i++) adj.clear();
scanf("%d %d",&i,&j);
while (!(i==0 && j==0))
{adj.push_back(j);
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]
I use BFS to solve it. I don't know why. Please help me, thanks.
[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();
for (k=0;k<adj.size();k++)
{v=adj[k];
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);
for (i=0;i<=n;i++) adj.clear();
scanf("%d %d",&i,&j);
while (!(i==0 && j==0))
{adj.push_back(j);
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]
I did not check your code throughly, but you could try something yourself.
With a little timeexpense, 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.
With a little timeexpense, 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.
top sort (WA)
Even I use topological sorting. But I always get WA.
any thing wrong with the algo?
abi
any thing wrong with the algo?
abi
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 .
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.
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 NPcomplete problem.
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 NPcomplete problem.
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 przypadek;
int tabela[110][110];
int sumy[110];
int konce[110];
int najm[110];
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;
przypadek=0;
while(1) {
cin >> ile_wezlow;
if (ile_wezlow==0) goto koniec;
inicjalizacja();
cin >> poczatek;
maks=0;
przypadek++;
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]
[cpp]
#include <iostream>
using namespace std;
int ile_wezlow;
int poczatek;
int maks;
int przypadek;
int tabela[110][110];
int sumy[110];
int konce[110];
int najm[110];
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;
przypadek=0;
while(1) {
cin >> ile_wezlow;
if (ile_wezlow==0) goto koniec;
inicjalizacja();
cin >> poczatek;
maks=0;
przypadek++;
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]

 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.
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