10816 - Travel in Desert

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

Moderator: Board moderators

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

10816 - Travel in Dessert - Runtime error

Post by thanhbuu » Wed Jun 22, 2011 6:12 pm

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];
long m,head[N],tr[N];
double d1[N],d2[N];
bool fr[N];
void adds(long u,long v,double x, double y)
{
  ++m; a[m].v=v; a[m].x=x; a[m].y=y; a[m].next=head[u]; head[u]=m;
  ++m; a[m].v=u; a[m].x=x; a[m].y=y; a[m].next=head[v]; head[v]=m;
}
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;
    long j=head[u];
    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;
    long i=head[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);
    memset(head,0,sizeof(head));
    m=0; long u,v; double x,y;
    for (long i=1;i<=e;i++) 
    {
      scanf("%ld %ld %lf %lf",&u,&v,&x,&y);
      adds(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

Post by thanhbuu » Wed Jun 22, 2011 6:13 pm

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];
long m,head[N],tr[N];
double d1[N],d2[N];
bool fr[N];
void adds(long u,long v,double x, double y)
{
  ++m; a[m].v=v; a[m].x=x; a[m].y=y; a[m].next=head[u]; head[u]=m;
  ++m; a[m].v=u; a[m].x=x; a[m].y=y; a[m].next=head[v]; head[v]=m;
}
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;
    long j=head[u];
    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;
    long i=head[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);
    memset(head,0,sizeof(head));
    m=0; long u,v; double x,y;
    for (long i=1;i<=e;i++) 
    {
      scanf("%ld %ld %lf %lf",&u,&v,&x,&y);
      adds(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

Post by prashantharshi » Wed Jul 09, 2014 8:10 am

#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> adj[max];
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();
int size=adj[s1.u].size();
for(int i=0;i<size;i++)
{
int vr=adj[s1.u][i].u;
if(adj[s1.u][i].r<=tmin)
{
if(dist[vr]>dist[s1.u]+adj[s1.u][i].d)
{

dist[vr]=dist[s1.u]+adj[s1.u][i].d;
pred[vr]=s1.u;
s s2={vr,adj[s1.u][i].r,dist[vr]};
q.push(s2);
}
}
}
}
}
int main()
{
while(cin>>n>>e)
{
cin>>sv>>ev;
for(int i=1;i<max;i++)
{
adj[i].clear();
}
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};
adj[x].push_back(s2);
s s3={x,r,d};
adj[y].push_back(s3);
}
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

Post by prashantharshi » Wed Jul 09, 2014 8:11 am

#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> adj[max];
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();
int size=adj[s1.u].size();
for(int i=0;i<size;i++)
{
int vr=adj[s1.u][i].u;
if(adj[s1.u][i].r<=tmin)
{
if(dist[vr]>dist[s1.u]+adj[s1.u][i].d)
{

dist[vr]=dist[s1.u]+adj[s1.u][i].d;
pred[vr]=s1.u;
s s2={vr,adj[s1.u][i].r,dist[vr]};
q.push(s2);
}
}
}
}
}
int main()
{
while(cin>>n>>e)
{
cin>>sv>>ev;
for(int i=1;i<max;i++)
{
adj[i].clear();
}
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};
adj[x].push_back(s2);
s s3={x,r,d};
adj[y].push_back(s3);
}
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

Post by brianfry713 » Wed Jul 09, 2014 9:10 pm

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

Post Reply

Return to “Volume 108 (10800-10899)”