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;
}
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