题解 UVA10816 【Travel in Desert】

· · 题解

题解

传送门：透彻

首先，说一下洛谷上翻译有坑，输入时是先输入温度r，再输入长度d。

因为要让最大值最小，所以很容易想到二分，但快NOIP了还是练了一下最小瓶颈路。

首先有两道最小瓶颈路的题货车运输，星际导航。

我们发现这道题有两个限制温度和长度，不好处理，所以我们要去消除一层限制。

因为要首先保证最高温度尽量小，所以先考虑温度。

有些经验的都应该能想到最小瓶颈路，跑出s到t的最高温度的最小值maxtem。

然后把温度不大于maxtem的边加入图中，跑最短路记录路径即可。

code：

#include<iostream>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#define N 10005
#define INF 0x3f3f3f3f
#define R register
using namespace std;
template<typename T>inline void read(T &a){
    char c=getchar();T x=0,f=1;
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    a=f*x;
}
int n,m,s,t,num,fa[N],tot,h[N];
double maxtem,dist[N];
bool vis[N];
vector<int> path;
struct MST{
    int u,v;
    double len,tem;
    friend bool operator < (const MST &a,const MST &b){
        return a.tem<b.tem;
    }
}tre[N];
struct node{
    int nex,to;
    double dis;
}edge[N<<1];
inline void add(R int u,R int v,R double w){
    edge[++tot].nex=h[u];
    edge[tot].to=v;
    edge[tot].dis=w;
    h[u]=tot;
}
inline void ins(R int u,R int v,R double w,R double t){
    tre[++num].u=u;
    tre[num].v=v;
    tre[num].len=w;
    tre[num].tem=t;
}
inline int find(R int x){
    if(x!=fa[x])fa[x]=find(fa[x]);
    return fa[x];
}
struct HeapNode{
    int u;
    double d;
    friend bool operator < (const HeapNode &a,const HeapNode &b){
        return a.d>b.d;
    }
};
priority_queue<HeapNode> q;
inline void dij(){
    for(R int i=1;i<=n;i++)dist[i]=INF,vis[i]=0,fa[i]=0;
    dist[s]=0;q.push((HeapNode){s,dist[s]});
    while(!q.empty()){
        R int x=q.top().u;q.pop();
        if(vis[x])continue;vis[x]=1;
        for(R int i=h[x];i;i=edge[i].nex){
            R int xx=edge[i].to;
            if(dist[xx]>dist[x]+edge[i].dis){
                dist[xx]=dist[x]+edge[i].dis;
                fa[xx]=x;
                q.push((HeapNode){xx,dist[xx]});
            }
        }
    }
    R int x=t;
    path.clear();
    while(x!=s){
        path.push_back(x);
        x=fa[x];
    }
    path.push_back(s);
    for(R int i=path.size()-1;i>=1;i--)
        printf("%d ",path[i]);
    printf("%d\n",path[0]);
}
int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        num=tot=0;maxtem=0;
        memset(h,0,sizeof(h));
        memset(fa,0,sizeof(fa));
        read(s);read(t);
        R double w,te;
        for(R int i=1,u,v;i<=m;i++){
            read(u);read(v);scanf("%lf%lf",&te,&w);
            ins(u,v,w,te);
        }
        for(R int i=1;i<=n;i++)fa[i]=i;
        sort(tre+1,tre+1+m);
        for(R int i=1;i<=m;i++){
            R int x=find(tre[i].u),y=find(tre[i].v);
            if(x!=y){
                fa[x]=y;
                maxtem=max(maxtem,tre[i].tem);
                if(find(s)==find(t))break;
            }
        }
        for(R int i=1;i<=m;i++){
            if(tre[i].tem>maxtem)break;;
            add(tre[i].u,tre[i].v,tre[i].len);
            add(tre[i].v,tre[i].u,tre[i].len);
        }
        dij();
        printf("%.1f %.1f\n",dist[t],maxtem);
    }
    return 0;
}