10816 - Travel in Desert

[thanhbuu]

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]

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]

#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]

#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]

Try solving it without using floating point.