341 - Non-Stop Travel

All about problems in Volume 3. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

oulongbin
Learning poster
Posts: 53
Joined: Sat Jul 10, 2004 5:57 pm
Location: Shanghai China

341 Non-Stop Travel

Post by oulongbin » Mon Jan 24, 2005 7:25 am

Hi,i used the "Dijkstra" to solve this problem,but got WA.i don't know why i was wrong,can somebody give me some special case??thank you .

Code: Select all

#include <iostream>
using namespace std; 
#include <cstdio> 
#include <cstring> 

#define MAXV 100
#define MAXDEGREE 100
#define MAXINT 99999

int parent[MAXV];
int del[MAXV][MAXV];
int cas=1;

typedef struct
{
	int v;
	int weight;
}edge;

typedef struct
{
	edge edges[MAXV+1][MAXDEGREE];
	int degree[MAXV+1];
	int nvertices;
}graph;

void init(graph *g,int n)
{
	int i,j;
	int x,y,z;
	for(i=1;i<=MAXV;i++)
		g->degree[i]=0;
	g->nvertices=n;
	for(i=1;i<=g->nvertices;i++)
	{
		cin>>z;
		for(j=0;j<z;j++)
		{
			cin>>x>>y;
			del[i][x]=y;
			g->edges[i][g->degree[i]].v=x;
			g->edges[i][g->degree[i]].weight=y;
			g->degree[i]++;
		}
	}
}

void dijkstra(graph *g,int start)
{
	int i;
	bool intree[MAXV];
	int distance[MAXV];
	
	int v;
	int w;
	int weight;
	int dist;

	for(i=1;i<=g->nvertices;i++)
	{
		intree[i]=false;
		distance[i]=MAXINT;
		parent[i]=-1;
	}
	distance[start]=0;
	v=start;

	while(intree[v]==false)
	{
		intree[v]=true;//把结点v放入树中
		for(i=0;i<g->degree[v];i++)//有几个相临结点
		{
			w=g->edges[v][i].v;//与结点v相邻的结点
			weight=g->edges[v][i].weight;//到该结点的权重
			if( distance[w]>(distance[v]+weight)  )
			{
				distance[w]=distance[v]+weight;
				parent[w]=v;
			}
		}
		v=1;
		dist=MAXINT;
		for(i=2;i<=g->nvertices;i++)
		{
			if( (intree[i]==false) && (dist>distance[i]) )
			{
				dist=distance[i];
				v=i;
			}
		}
	}
}

void output(graph *g,int start,int end)
{
	int delay;
	int te;
	int pass[MAXV];
	int realpass[MAXV];
	int i,j,k;
	te=end;
	delay=0;
	i=0;
	k=0;
	realpass[k++]=start;
	while(parent[end]!=start)
	{
		pass[i++]=parent[end];
		end=parent[end];
	}
	for(j=i-1;j>=0;j--)
	{
		realpass[k++]=pass[j];
	}
	realpass[k]=te;
	cout<<"Case "<<cas++<<": Path = ";
	for(i=0;i<k;i++)
	{
		cout<<realpass[i]<<" ";
		delay+=del[realpass[i]][realpass[i+1]];
	}
	cout<<realpass[i]<<"; "<<delay<<" second delay"<<endl;
}

int  main() 
{ 
	graph g;
	int n;
	int i;
	int start,end;
	while(cin>>n&&n!=0)
	{
		init(&g,n);
		cin>>start>>end;
		dijkstra(&g,start);
		output(&g,start,end);
	}
    return 0; 
} 


TISARKER
Learning poster
Posts: 88
Joined: Tue Oct 12, 2004 6:45 pm
Location: Bangladesh
Contact:

341 - Non-Stop Travel

Post by TISARKER » Fri Dec 23, 2005 11:19 am

I have been getting wrong answer for 1 year. :evil: Can anyone tell me, why?
My Algorithm is
=================
1.Take input.
2.Use Floydwarshal or Diskstra for finding Shortest path.
3.Display path and minimum delay time.
=======================================
What is the output for following input

Code: Select all

3
1 2 5
1 3 5
1 1 5
1 1
0
Is there any tricky input for this problem.?
If exists please give those?
Last edited by TISARKER on Sat Dec 24, 2005 7:15 am, edited 1 time in total.
Mr. Arithmetic logic Unit

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon » Fri Dec 23, 2005 11:07 pm

I did the same thing. Here's my output.

Code: Select all

Case 1: Path = 1; 0 second delay

TISARKER
Learning poster
Posts: 88
Joined: Tue Oct 12, 2004 6:45 pm
Location: Bangladesh
Contact:

Post by TISARKER » Sat Dec 24, 2005 7:11 am

Code: Select all

Remove After Accepted
Last edited by TISARKER on Sun Dec 25, 2005 2:32 pm, edited 1 time in total.
Mr. Arithmetic logic Unit

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon » Sat Dec 24, 2005 7:56 pm

I believe that your floyd_warshall_spath() and show() are incorrect.

Here are my corrections to your code.

Code: Select all

void show(type i,type j,type path[range][range])
{
if(i!=j) show(i,path[i][j],path);
printf(" %ld",j+1);
} 

Code: Select all

void floyd_warshall_spath(dtype graph[range][range],dtype path[range][range],type n)
{
type i,j,k;

for(k=0;k<n;k++)for(i=0;i<n;i++)for(j=0;j<n;j++)
if((graph[i][k]+graph[k][j])<graph[i][j])
   {   path[i][j]=path[k][j];   graph[i][j]=graph[i][k]+graph[k][j]; }
} 

TISARKER
Learning poster
Posts: 88
Joined: Tue Oct 12, 2004 6:45 pm
Location: Bangladesh
Contact:

Post by TISARKER » Sun Dec 25, 2005 2:34 pm

THANKS :lol:
Mr. Arithmetic logic Unit

User avatar
Tanu
Learning poster
Posts: 70
Joined: Sun May 29, 2005 12:46 pm
Location: Mars

341 is it okey

Post by Tanu » Wed Apr 26, 2006 7:19 am

i'm trying to solve 341...
here is my code

Code: Select all

#include<stdio.h>
long G[12][12];
long x[15],ans[15];
long mincost,step;
void bfs(long s,long k,long N,long d)
{
	int i,sum = 0;
	
	x[k] = s;
	for(i = 1;i<=k;i++)
		sum += G[x[i-1]][x[i]];
	if(sum>mincost)
		return;
	
	if(s == d)
	{
		for(i = 0; i<=k ;i++)
			ans[i] = x[i];
		mincost = sum;
		step = k;
	}
	else
	{
		
		for(i = 1;i<=N;i++)
			if(G[s][i])
				bfs(i,k+1,N,d);
	}
}
main()
{
	long N,P,n,p,dest,start,test=1;
	//freopen("c:\in.txt","r",stdin);
	while(1)
	{
		scanf("%ld",&N);
		if(N == 0)
			break;

		for(n = 1;n<=N;n++)			for(p = 1;p<=N;p++)				G[n][p] = 0;
		mincost = 2147483647;
		for(n = 1;n<=N;n++)
		{
			
			scanf("%ld",&P);
			for(p = 1;p<=P;p++)	
			{
				scanf("%ld",&dest);
				scanf("%ld",&G[n][dest]);			
			}			
		}
		scanf("%ld%ld",&start,&dest);

		bfs(start,0,N,dest);
		printf("Case %ld: Path =",test++);
		for(p = 0;p<=step;p++)
			printf(" %ld",ans[p]);
		printf("; %ld second delay\n",mincost);
	}
	return 0;
}
is this way okey for this...
I'm getting wrong answer...
special input will be helpful...
plz help...
Thanx in advance...

soddy
New poster
Posts: 23
Joined: Tue May 29, 2007 1:39 am

341 - WA

Post by soddy » Thu Jan 31, 2008 11:05 pm

I am continuously getting WA in this problem. This seems to be a simple problem. I am using Floyd Warshall to find the shortest path distance and then backtracking to get the path. Can anybody help?

Code: Select all

Removed after AC
Last edited by soddy on Fri Feb 01, 2008 6:48 pm, edited 1 time in total.
I am not selfish, I just want everything.

greve
New poster
Posts: 27
Joined: Tue May 29, 2007 8:52 pm
Contact:

Post by greve » Fri Feb 01, 2008 9:11 am

You do not print the path correctly. Check the input below.

3
1 3 5
0
1 2 5
1 2

0
For help with problems, visit http://www.uvatoolkit.com/

soddy
New poster
Posts: 23
Joined: Tue May 29, 2007 1:39 am

Post by soddy » Fri Feb 01, 2008 6:46 pm

Thanx...I got AC :D
I am not selfish, I just want everything.

mirage
New poster
Posts: 11
Joined: Sat Jan 19, 2008 9:37 pm

gettin WA

Post by mirage » Fri Feb 22, 2008 8:03 pm

hi friends...
i m gettin a wrong answer for this problem.....
i tried the test cases i had nd it worked out fine....
is thr ny spcl case.....
plz help ....
here's the code

Code: Select all

//non stop travel
#include<iostream>
using namespace std;
int arr[10][10];
void process(int,int,int);
void print(int[],int);
int main(){
	int n;
	int count=1;
	while(cin>>n){
		if(n==0) return(0);
		int i=0,j=0;
		while(i<n){
			j=0;
			while(j<n) arr[i][j++]=100000000;
			i++;
		}
		i=0;
		while(i<n){
			int k;
			cin>>k;
			while(k>0){
				int a,b;
				cin>>a>>b;
				arr[i][a-1]=b;
				k--;
			}
			i++;
		}
		int source,desti;
		cin>>source>>desti;
		//process
		cout<<"Case "<<count++<<": ";
		process(source-1,desti-1,n);
	}
}
void process(int s,int de,int l){
	int ar[10];
	int mark[10];
	int prev[10];
	int i=0;
	while(i<l){
		ar[i]=100000000;
		mark[i++]=0;
	}
	ar[s]=0;
	mark[s]=1;
	int mins=s;
	int loop=1;
	while(loop<l){
		//set accordin to mins
		int j=0;
		int min=100000000,minin;
		while(j<l){
			int d=arr[mins][j]+ar[mins];
			if(mark[j]==0){
				if(ar[j]>d) {
					ar[j]=d;
					prev[j]=mins;
				}
				if(ar[j]<min) {min=ar[j];minin=j;}
			}
			j++;
		}
		mins=minin;
		mark[mins]=1;
		loop++;
	}
	string path="";
	int r=de;
	while(r!=s){
		path=char(r+'1')+path;
		path=" "+ path;
		r=prev[r];
	}
	path=char(s+'1')+path;
	cout<<"Path = "<<path<<"; "<<ar[de]<<" second delay"<<"\n";
	return;
}
void print(int a[],int len){
	int i=0;
	while(i<len) cout<<a[i++]<<" ";
	cout<<"\n";
	return;
}

skysdakop
New poster
Posts: 1
Joined: Wed May 14, 2008 7:19 pm

Re: 341 - WA

Post by skysdakop » Wed May 14, 2008 7:30 pm

Can anyone help me with this problem? I am using Diskstra and got WA every time..

My code:

Code: Select all


#include <iostream>
#include <list>
#include <stdio.h>

using namespace std;

int main(int argc, char **argv)
{
	int cases = 1, nvert;
	
inicio:
	cin >> nvert;
	if(nvert == 0)
		return 0;
	
	
	int vet[11][11];
	

	// zerar caminhos
	for(int i = 0; i < 11; i++)
	{
		for(int x = 0; x < 11; x++)
		{
			vet[i][x] = 50001;
		}
	}
	
	int path[11];
	for(int i = 0; i < 11; i++)
		path[i] = -1;
	
	int dist[11];
	for(int i = 0; i < 11; i++)
		dist[i] = 50001;
	
	int to, from, numlig;
	int delay;
	

	// entrada
	for(int i = 1; i <= nvert; i++)
	{
		cin >> numlig;
		for(int x = 1; x <= numlig; x++)
		{
			cin >> to >> delay;
			vet[i][to] = delay;
			
			//printf("delay de %d - %d = %d\n", i, to, vet[i][to]);
		}
	}
	
	cin >> from >> to;
	
	list<int> l;
	
	l.push_back(from);
	
	dist[from] = 0;
	
	int atual;
	
	//printf("lsize: %d\n", l.size());
	while(l.size() != 0)
	{
		atual = l.front();
		l.pop_front();
		
		//printf("lsize: %d analisando: %d\n", l.size(), atual);
		
		//exit(0);
		
		for(int i = 1; i <= 10; i++)
		{
			// tiver setado um delay
			if(vet[atual][i] != 50001)
			{
				//printf("vet[%d][%d] = %d\n", atual, i, vet[atual][i]);
				// se ele ainda n tiver sido percorrido
				// adicionar ele na lista
				if(path[i] == -1 && i != to)
				{
					l.push_back(i);
				}
				
				int distancia = vet[atual][i] + dist[atual];
				
				// se o delay ja setado for maior que o atual
				if(dist[i] > distancia)
				{
					dist[i] = distancia;
					path[i] = atual;
					
					//printf("dist[%d] = %d\n", i, dist[i]);
				}
			}
		}
	}	
	
	cout << "Case " << cases << ": Path =";
	atual = to;
	list<int> caminho;
	
	do
	{
		caminho.push_front(atual);
		atual = path[atual];
	} while(atual != -1);

	if(caminho.size() == 1)
	{
		caminho.push_front(caminho.front());
	}
	
	list<int>::iterator k = caminho.begin();
	for(; k != caminho.end(); k++)
	{
		cout << " " << *k;
	}
	
	cout << "; " << dist[to] << " second delay" << endl;
	cases++;
	goto inicio;
	
	return 0;
}


fernandohbc
New poster
Posts: 5
Joined: Sat Aug 14, 2010 10:31 pm

Got a WA

Post by fernandohbc » Sat Aug 14, 2010 10:35 pm

I tried to do this using FloydWarshall but got no hope. Always WA.
Tried all sample inputs from this board and my code seems to get it right in every attempt.

Can you guys help me?

Code: Select all

package volume_iii;

import java.util.Scanner;

public class P341_3747 {
    public static void main(String[] args) {
        new P341_3747().begin();
    }

    private long[][] graph;
    private int[][] intermediate;
    private int v;
    private static final long INFINITE = 67108864;

    private void begin() {
        Scanner scn = new Scanner(System.in);
        v = scn.nextInt();
        int tc = 1;
        while (v != 0 ) {
            //Lê o grafo
            initGraph(v);

            for ( int i = 1; i <= v; i++ ) {
                int e = scn.nextInt();
                for ( int j = 0; j < e; j++ ) {
                    int w = scn.nextInt();
                    int peso = scn.nextInt();
                    graph[i][w] = peso;
                }
            }

            floydWarshall();

            int from = scn.nextInt();
            int to = scn.nextInt();

            System.out.println("Case " + (tc++) + ": Path = " + getPath(from,to) + "; " + graph[from][to] + " second delay");

            v = scn.nextInt();
        }
    }

    private String getPath(int from, int to) {
        int e = intermediate[from][to];
        if ( e == 0 ) {
            return from + " " + to;
        } else {
            return getPath(from, e) + getPath(e, to).substring(1);
        }
    }

    private void floydWarshall() {
        intermediate = new int[v+1][v+1];
        for ( int k = 1; k <= v; k++ ) {
            for ( int i = 1; i <= v; i++ ) {
                for ( int j = 1; j <= v; j++ ) {
                    if ( graph[i][k]+graph[k][j] < graph[i][j] ) {
                        graph[i][j] = graph[i][k]+graph[k][j];
                        intermediate[i][j] = k;
                    }
                }
            }
        }
    }

    private void initGraph(int v) {
        graph = new long[v+1][v+1];
        for ( int i = 1; i <= v; i++ ) {
            for ( int j = 1; j <= v; j++ ) {
                if ( i != j ) {
                    graph[i][j] = INFINITE;
                }
            }
        }
    }
}

asraful.ruet
New poster
Posts: 5
Joined: Wed Aug 11, 2010 8:52 am

341 Non-Stop Travel

Post by asraful.ruet » Sun Sep 12, 2010 1:01 pm

Please Help !
Whats wrong with my code ?
Thanks in advance .

Code: Select all

#include<stdio.h>
#define INF 2147483647

long i[15][15],d,path[15];

void inter(long a, long b){
 if(i[a][b]!=0){
   inter(a,i[a][b]);
   inter(i[a][b],b);
   path[++d]= i[a][b];
   }
}

int main(){

long c[15][15],j,k,l,n,m,p,q,kase=0;

while(scanf("%ld",&n)&&n){
       d=0;

      for(l=1;l<=n;++l){
        for(k=1;k<=n;++k){
          c[l][k]=INF;
          i[l][k]=0;
         }
       }

      for(l=1;l<=14;++l)
        path[l]=0;

      for(j=1;j<=n;++j){
        scanf("%ld",&m);
       for(l=1;l<=m;++l){
         scanf("%ld%ld",&p,&q);
         c[j][p]=q;
        }
      }

scanf("%ld%ld",&p,&q);

for(k=1;k<=n;++k){
 for(l=1;l<=n;++l){
   for(j=1;j<=n;++j){
    if(c[l][k]!=INF && c[k][j]!=INF && l!=j){
     if( c[l][j] > ( c[l][k]+c[k][j] )){
         c[l][j] = c[l][k]+c[k][j];
         i[l][j]=k;
     }
    }
   }
  }
 }


inter(p,q);

printf("Case %ld: Path = %ld ",++kase,p);

  for(l=1;l<=d;++l)
    printf("%ld ",path[l]);

printf("%ld; %ld second delay\n",q,c[p][q]);


}
 return 0;
}



spewer
New poster
Posts: 4
Joined: Tue Dec 20, 2011 4:04 pm

Re: 341 Non-Stop Travel

Post by spewer » Wed Dec 21, 2011 11:17 pm

Try this input

Code: Select all

5
2  3 3   4 6
3  1 2   3 7   5 6
1  4 5
0
1  4 7
2 2

2
1   2 5
1   1 6
1 2

7
4   2 5   3 13   4 8   5 18
2   3 7   6 14
1   6 6
2   3 5   5 9
3   6 2   7 9    4 6
1   7 2
0
1 7

0

Answer should be this

Code: Select all

Case 1: Path = 2 2; 0 second delay
Case 2: Path = 1 2; 5 second delay
Case 3: Path = 1 2 3 6 7; 20 second delay

Post Reply

Return to “Volume 3 (300-399)”