Uva-10816-Travel in Desert

하루 가까이 끊겼더니 출력 답이 거꾸로 나왔다.
방법은 w온도치를 2분 1로 매거한 다음 Spfa를 달리는 것이다
코드:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const double eps=1e-8;
const int inf=1<<29;
const int maxn=1010;
const int maxm=2e5+100;
int e,n,m,st,des,head[maxn],nxt[maxm],pnt[maxm],pre[maxn],costr[maxm],costd[maxm],dist[maxn];
bool vis[maxn];
queue<int> q;
void AddEdge(int u,int v,int cr,int cd)
{
    pnt[e]=v;nxt[e]=head[u];costr[e]=cr;costd[e]=cd;head[u]=e++;
    pnt[e]=u;nxt[e]=head[v];costr[e]=cr;costd[e]=cd;head[v]=e++;
}
void DFS(int u)
{
    if(u==st)
    {
        printf("%d",st);
        return;
    }
    DFS(pre[u]);
    printf(" %d",u);
}
bool Spfa(int st,int des,int val)
{
    memset(pre,-1,sizeof(pre));
    for(int i=0;i<=n;i++)
        dist[i]=inf;
    dist[st]=0;
    q.push(st);
    while(!q.empty())
    {
        int u=q.front();
        vis[u]=0;
        q.pop();
        for(int i=head[u];i!=-1;i=nxt[i])
        {
            if(costr[i]<=val&&dist[pnt[i]]>dist[u]+costd[i])
            {
                dist[pnt[i]]=dist[u]+costd[i];
                pre[pnt[i]]=u;
                if(!vis[pnt[i]])
                {
                    q.push(pnt[i]);
                    vis[pnt[i]]=1;
                }
            }
        }
    }
    if(dist[des]!=inf)
        return true;
    return false;
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        e=0;
        memset(head,-1,sizeof(head));
        scanf("%d%d",&st,&des);
        int sl=inf,sr=0;
        for(int i=0;i<m;i++)
        {
            int u,v,r,d;
            int sa1,sa2,sb1,sb2;
            scanf("%d%d%d.%d%d.%d",&u,&v,&sa1,&sa2,&sb1,&sb2);
            r=sa1*10+sa2;
            d=sb1*10+sb2;
            AddEdge(u,v,r,d);
            sl=min(sl,r);
            sr=max(sr,r);
        }
        int ans=0;
        while(sl<=sr)
        {
            int mid=(sl+sr)>>1;
            if(Spfa(st,des,mid))
            {
                ans=mid;
                sr=mid-1;
            }
            else
                sl=mid+1;
        }
        Spfa(st,des,ans);
        DFS(des);
        printf("
");
        printf("%.1f %.1f
",dist[des]*1.0/10,ans*1.0/10);
    }
    return 0;
}