## 341 - Non-Stop Travel

Moderator: Board moderators

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

### 341 Non-Stop Travel

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
Contact:

### 341 - Non-Stop Travel

I have been getting wrong answer for 1 year. 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.?
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
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
Contact:

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
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
Contact:
THANKS
Mr. Arithmetic logic Unit

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

### 341 is it okey

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

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

### 341 - WA

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:
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
Thanx...I got AC
I am not selfish, I just want everything.

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

### gettin WA

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

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;

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++)
{
if(vet[atual][i] != 50001)
{
//printf("vet[%d][%d] = %d\n", atual, i, vet[atual][i]);
// se ele ainda n tiver sido percorrido
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

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

Whats wrong with my code ?

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

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


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