## 10816 - Travel in Desert

Moderator: Board moderators

thanhbuu
New poster
Posts: 3
Joined: Sun Jun 19, 2011 3:24 pm

### 10816 - Travel in Dessert - Runtime error

Code: Select all

``````#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <climits>
#include <string>
#define oo LONG_MAX
#define fi "10816.INP"
#define fo "10816.OUT"
#define N 1001
#define E 100001
#define EPS 1E-12
using namespace std;
struct dl { long v,next; double x,y; } a[E*2];
double d1[N],d2[N];
bool fr[N];
void adds(long u,long v,double x, double y)
{
}
void MST(long s,long t,long n)
{
//length d2
//temparature d1
for (long i=0;i<=n;i++) d1[i]=oo,d2[i]=oo;
memset(fr,true,sizeof(fr));
d1[s]=0; d2[s]=0; tr[s]=-1;
for (long k=1;k<=n;k++)
{
long u=0;
for (long i=1;i<=n;i++) if (d1[u]>d1[i] && fr[i]) u=i;
fr[u]=false;
while (j!=0)
{
long v=a[j].v;
if (fr[v])
if (d1[v]>max(a[j].x,d1[u])) d1[v]=max(a[j].x,d1[u]),d2[v]=d2[u]+a[j].y,tr[v]=u;
else if (d1[v]==max(a[j].x,d1[u]) && d2[v]>d2[u]+a[j].y) d2[v]=d2[u]+a[j].y,tr[v]=u;
j=a[j].next;
}
}
long v=n,output[N],sl=0;
double kq=0,tmp;
while (tr[v]!=-1)
{
output[sl++]=v;
tmp=oo;
while (i!=0)
{
if (a[i].x<=d1[n] && tmp>a[i].y && a[i].v==tr[v]) tmp=a[i].y;
i=a[i].next;
}
kq+=tmp;
v=tr[v];
}
output[sl]=1;
sort(output,output+sl+1);
for (long i=0;i<sl;i++) printf("%ld ",output[i]); printf("%ld",output[sl]);
printf("\n%0.1lf %0.1lf\n",kq,d1[n]);
}
void input()
{
long n,e,s,t;
while (scanf("%ld %ld",&n,&e)==2)
{
scanf("%ld %ld",&s,&t);
m=0; long u,v; double x,y;
for (long i=1;i<=e;i++)
{
scanf("%ld %ld %lf %lf",&u,&v,&x,&y);
}
MST(s,t,n);
}
}
int main()
{
input();
return 0;
}
``````
can someone explain me about the Runtime Error - I can't find where made my program became RE, thanks
Hi,

This is an automated response from UVa Online Judge.

Your submission with number 8977263 for the problem 10816 - Travel in Desert has failed with verdict Runtime error.

This means that the execution of your program didn't finish properly. Remember to always terminate your code with the exit code 0.

Best regards,

The UVa Online Judge team

thanhbuu
New poster
Posts: 3
Joined: Sun Jun 19, 2011 3:24 pm

### 10816 - Travel in Dessert - Runtime error

Code: Select all

``````#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <climits>
#include <string>
#define oo LONG_MAX
#define fi "10816.INP"
#define fo "10816.OUT"
#define N 1001
#define E 100001
#define EPS 1E-12
using namespace std;
struct dl { long v,next; double x,y; } a[E*2];
double d1[N],d2[N];
bool fr[N];
void adds(long u,long v,double x, double y)
{
}
void MST(long s,long t,long n)
{
//length d2
//temparature d1
for (long i=0;i<=n;i++) d1[i]=oo,d2[i]=oo;
memset(fr,true,sizeof(fr));
d1[s]=0; d2[s]=0; tr[s]=-1;
for (long k=1;k<=n;k++)
{
long u=0;
for (long i=1;i<=n;i++) if (d1[u]>d1[i] && fr[i]) u=i;
fr[u]=false;
while (j!=0)
{
long v=a[j].v;
if (fr[v])
if (d1[v]>max(a[j].x,d1[u])) d1[v]=max(a[j].x,d1[u]),d2[v]=d2[u]+a[j].y,tr[v]=u;
else if (d1[v]==max(a[j].x,d1[u]) && d2[v]>d2[u]+a[j].y) d2[v]=d2[u]+a[j].y,tr[v]=u;
j=a[j].next;
}
}
long v=n,output[N],sl=0;
double kq=0,tmp;
while (tr[v]!=-1)
{
output[sl++]=v;
tmp=oo;
while (i!=0)
{
if (a[i].x<=d1[n] && tmp>a[i].y && a[i].v==tr[v]) tmp=a[i].y;
i=a[i].next;
}
kq+=tmp;
v=tr[v];
}
output[sl]=1;
sort(output,output+sl+1);
for (long i=0;i<sl;i++) printf("%ld ",output[i]); printf("%ld",output[sl]);
printf("\n%0.1lf %0.1lf\n",kq,d1[n]);
}
void input()
{
long n,e,s,t;
while (scanf("%ld %ld",&n,&e)==2)
{
scanf("%ld %ld",&s,&t);
m=0; long u,v; double x,y;
for (long i=1;i<=e;i++)
{
scanf("%ld %ld %lf %lf",&u,&v,&x,&y);
}
MST(s,t,n);
}
}
int main()
{
input();
return 0;
}
``````
can someone explain me about the Runtime Error - I can't find where made my program became RE, thanks
Hi,

This is an automated response from UVa Online Judge.

Your submission with number 8977263 for the problem 10816 - Travel in Desert has failed with verdict Runtime error.

This means that the execution of your program didn't finish properly. Remember to always terminate your code with the exit code 0.

Best regards,

The UVa Online Judge team

prashantharshi
New poster
Posts: 22
Joined: Wed May 21, 2014 10:16 am

### Re: 10816 - Travel in Desert

#include<iostream>
#include<stdio.h>
#include<vector>
#include<queue>
#include<string.h>
#include<algorithm>
#include<iomanip>
#define max 110
using namespace std;
int n,e,sv,ev,x,y;
float r,d,tmin;
float dist[max];
int pred[max];
int status[max];
struct set
{
int parent;
int rank;
};
struct st
{
int u;
int v;
float r;
float d;
};
struct s
{
int u;
float r;
float d;
};
struct compare
{
bool operator()(const st& s1,const st& s2)
{
return s1.r>s2.r;
}
};
struct cmp
{
bool operator()(const s& s1,const s& s2)
{
return dist[s1.u]>dist[s1.u];
}
};
priority_queue<st,vector<st>,compare> pq;
priority_queue<s,vector<s>,cmp> q;
vector<s> gr[max];
queue<s> q1;
set arr[max];
void init()
{
for(int i=0;i<max;i++)
{
arr.parent=i;
arr.rank=0;
}
}
int find(int x)
{
if(arr[x].parent!=x)
arr[x].parent=find(arr[x].parent);
return arr[x].parent;
}
void Union(int r1,int r2)
{
int xroot=find(r1);
int yroot=find(r2);
if(arr[xroot].rank>arr[yroot].rank)
arr[yroot].parent=xroot;
else if(arr[xroot].rank<arr[yroot].rank)
arr[xroot].parent=yroot;
else
{
arr[yroot].parent=xroot;
arr[xroot].rank++;
}
}
void kruskal()
{
init();
for(int i=1;i<max;i++)
{
gr.clear();
}
while(!pq.empty())
{
st s1=pq.top();
pq.pop();
int u=s1.u;
int v=s1.v;
if(find(u)!=find(v))
{
s t1={s1.v,s1.r,s1.d};
gr[s1.u].push_back(t1);
s t2={s1.u,s1.r,s1.d};
gr[s1.v].push_back(t2);
Union(s1.u,s1.v);
}
}
}
float minimax()
{
while(!q1.empty())
{
q1.pop();
}
memset(status,0,sizeof(status));
s s1={sv,0,0};
status[sv]=0;
q1.push(s1);
while(!q1.empty())
{
s s1=q1.front();
q1.pop();
if(s1.u==ev)
return s1.r;
status[s1.u]=1;
for(int i=0;i<gr[s1.u].size();i++)
{
int v=gr[s1.u].u;
if(!status[v])
{
if(gr[s1.u].r>s1.r)
{
s s2={v,gr[s1.u].r,gr[s1.u].d};
q1.push(s2);
}
else
{
s s2={v,s1.r,gr[s1.u].d};
q1.push(s2);
}
}
}
}
}
float dijkstra()
{
for(int i=1;i<max;i++)
{
dist=999999999.99;
pred=-1;
}
while(!q.empty())
{
q.pop();
}
s s1={sv,0,0};
q.push(s1);
dist[sv]=0;
pred[sv]=-1;
while(!q.empty())
{
s s1=q.top();
if(s1.u==ev)
return dist[ev];
q.pop();
for(int i=0;i<size;i++)
{
{
{

pred[vr]=s1.u;
q.push(s2);
}
}
}
}
}
int main()
{
while(cin>>n>>e)
{
cin>>sv>>ev;
for(int i=1;i<max;i++)
{
}
for(int i=1;i<=e;i++)
{
cin>>x>>y>>r>>d;
st s1={x,y,r,d};
pq.push(s1);
s s2={y,r,d};
s s3={x,r,d};
}
kruskal();
float k=minimax();
tmin=k;
float dis=dijkstra();
vector<int> v;
int vr=ev;
while(pred[vr]!=-1)
{
v.push_back(vr);
vr=pred[vr];
}
v.push_back(vr);
reverse(v.begin(),v.end());
for(int i=0;i<v.size();i++)
{
cout<<v[i]<<" ";
}
cout<<"\n";
v.clear();

printf("%.1f %.1f\n", dis,k);
}
return 0;
}

prashantharshi
New poster
Posts: 22
Joined: Wed May 21, 2014 10:16 am

### Re: 10816 - Travel in Desert

#include<iostream>
#include<stdio.h>
#include<vector>
#include<queue>
#include<string.h>
#include<algorithm>
#include<iomanip>
#define max 110
using namespace std;
int n,e,sv,ev,x,y;
float r,d,tmin;
float dist[max];
int pred[max];
int status[max];
struct set
{
int parent;
int rank;
};
struct st
{
int u;
int v;
float r;
float d;
};
struct s
{
int u;
float r;
float d;
};
struct compare
{
bool operator()(const st& s1,const st& s2)
{
return s1.r>s2.r;
}
};
struct cmp
{
bool operator()(const s& s1,const s& s2)
{
return dist[s1.u]>dist[s1.u];
}
};
priority_queue<st,vector<st>,compare> pq;
priority_queue<s,vector<s>,cmp> q;
vector<s> gr[max];
queue<s> q1;
set arr[max];
void init()
{
for(int i=0;i<max;i++)
{
arr.parent=i;
arr.rank=0;
}
}
int find(int x)
{
if(arr[x].parent!=x)
arr[x].parent=find(arr[x].parent);
return arr[x].parent;
}
void Union(int r1,int r2)
{
int xroot=find(r1);
int yroot=find(r2);
if(arr[xroot].rank>arr[yroot].rank)
arr[yroot].parent=xroot;
else if(arr[xroot].rank<arr[yroot].rank)
arr[xroot].parent=yroot;
else
{
arr[yroot].parent=xroot;
arr[xroot].rank++;
}
}
void kruskal()
{
init();
for(int i=1;i<max;i++)
{
gr.clear();
}
while(!pq.empty())
{
st s1=pq.top();
pq.pop();
int u=s1.u;
int v=s1.v;
if(find(u)!=find(v))
{
s t1={s1.v,s1.r,s1.d};
gr[s1.u].push_back(t1);
s t2={s1.u,s1.r,s1.d};
gr[s1.v].push_back(t2);
Union(s1.u,s1.v);
}
}
}
float minimax()
{
while(!q1.empty())
{
q1.pop();
}
memset(status,0,sizeof(status));
s s1={sv,0,0};
status[sv]=0;
q1.push(s1);
while(!q1.empty())
{
s s1=q1.front();
q1.pop();
if(s1.u==ev)
return s1.r;
status[s1.u]=1;
for(int i=0;i<gr[s1.u].size();i++)
{
int v=gr[s1.u].u;
if(!status[v])
{
if(gr[s1.u].r>s1.r)
{
s s2={v,gr[s1.u].r,gr[s1.u].d};
q1.push(s2);
}
else
{
s s2={v,s1.r,gr[s1.u].d};
q1.push(s2);
}
}
}
}
}
float dijkstra()
{
for(int i=1;i<max;i++)
{
dist=999999999.99;
pred=-1;
}
while(!q.empty())
{
q.pop();
}
s s1={sv,0,0};
q.push(s1);
dist[sv]=0;
pred[sv]=-1;
while(!q.empty())
{
s s1=q.top();
if(s1.u==ev)
return dist[ev];
q.pop();
for(int i=0;i<size;i++)
{
{
{

pred[vr]=s1.u;
q.push(s2);
}
}
}
}
}
int main()
{
while(cin>>n>>e)
{
cin>>sv>>ev;
for(int i=1;i<max;i++)
{
}
for(int i=1;i<=e;i++)
{
cin>>x>>y>>r>>d;
st s1={x,y,r,d};
pq.push(s1);
s s2={y,r,d};
s s3={x,r,d};
}
kruskal();
float k=minimax();
tmin=k;
float dis=dijkstra();
vector<int> v;
int vr=ev;
while(pred[vr]!=-1)
{
v.push_back(vr);
vr=pred[vr];
}
v.push_back(vr);
reverse(v.begin(),v.end());
for(int i=0;i<v.size();i++)
{
cout<<v[i]<<" ";
}
cout<<"\n";
v.clear();

printf("%.1f %.1f\n", dis,k);
}
return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10816 - Travel in Desert

Try solving it without using floating point.
Check input and AC output for thousands of problems on uDebug!