Travel in desert

不算难吧

应该有思路的

还是太水了吧

（而且和货车运输很像的啊

----------------------------------------------------------------------------------------

题目大意

沙漠中有n 个绿洲（编号为1−n ）和e 条连接绿洲的双向道路。每条道路都有一个长度d 和一个温度值r 。给定起点绿洲编号sss 和终点绿洲编号ttt ，求出一条sss 到ttt 的路径，使得这条路径上经过的所有道路的最高温度尽量小，如果有多条路径，选择总长度最短的那一条。

输入格式

输入包含多组数据。

每组数据第一行为两个整数n 和e 。表示绿洲数量和连接绿洲的道路数量。

每组数据第二行为两个整数s 和t 。表示起点和终点的绿洲编号。

接下来e 行，每行包含两个整数x,y 以及两个实数r,d，表明在绿洲x 和y 之间有一条双向道路相连，长度为d ，温度为r 。

输出格式

对于输入的每组数据，应输出两行，第一行表示你找到的路线，第二行包含两个实数，为你找出的路线的总长度与途经的最高温度。

----------------------------------------------------------------------------------------

如果只考虑最小的最大热度

那么本题就是一个最小瓶颈路问题

只需按照热度找一棵最小生成树即可。

但是，如果这样的路径有多个，

实际上是最小生成树有多个时，

要找到最短路径，

还得把热度不大于最小生成树中最大热度的边并且没在生成树中的边加到最小生成树中，

然后再找最短路。

#include<cstdio>

#include<cctype>

#include<algorithm>

#include<cstring>

#include<queue>

#include<vector>

#define INF 0x3f3f3f3f

using namespace std;

inline int read()

{

    int sum = ,p = ;

    char ch = getchar();

    while(ch < '' || ch > '')

    {

        if(ch == '-')

            p = -;

        ch = getchar();

    }

    while(ch >= '' && ch <= '')

    {

        (sum *= ) += ch - '';

        ch = getchar();

    }

    return sum * p;

}

const int maxm = ;

int n,m,s,t;

double tmp;

struct edge

{

    int x,y;

    double d,r;

} e[maxm];

int fa[];

struct edgee

{

    int nxt,to;

    double wei;

} ed[maxm * ];

int cnt,head[];

double dis[];

struct node

{

    int u;

    double d;

    friend bool operator < (const node &a,const node &b)

    {

        return a.d > b.d;

    }

};

priority_queue<node> q;

bool mrk[];

vector<int> path;

bool cmp(edge a,edge b)

{

    return a.r < b.r;

}

int findfa(int o)

{

    if(o == fa[o])    return o;

    else    return fa[o] = findfa(fa[o]);

}

void kruskal()

{

    for(int i = ; i <= n; i++)

        fa[i] = i;

    sort(e+,e+m+,cmp);

    for(int i = ; i <= m; i++)

    {

        int u = findfa(e[i].x);

        int v = findfa(e[i].y);

        if(u == v)

            continue;

        fa[u] = v;

        tmp = max(tmp,e[i].r);

        if(findfa(s) == findfa(t))

            break;

    }

}

void add(int a,int b,double c)

{

    ed[++cnt].nxt = head[a];

    ed[cnt].to = b;

    ed[cnt].wei = c;

    head[a] = cnt;

}

void dijkstra()

{

    for(int i = ; i <= m; i++)

    {

        if(e[i].r > tmp)

            break;

        add(e[i].x,e[i].y,e[i].d);

        add(e[i].y,e[i].x,e[i].d);

    }

    for(int i = ;i <= n;i++)

        dis[i] = INF,fa[i] = ,mrk[i] = ;

    dis[s] = ;

    q.push((node){s,dis[s]});

    while(q.size())

    {

        int u = q.top().u;

        q.pop();

        if(mrk[u])

            continue;

        mrk[u] = true;

        for(int i = head[u]; i; i = ed[i].nxt)

        {

            int v = ed[i].to;

            double z = ed[i].wei;

            if(dis[v] > dis[u] + z)

            {

                dis[v] = dis[u] + z;

                fa[v] = u;

                q.push((node){v,dis[v]});

            }

        }

    }

    int x = t;

    path.clear();

    while(x != s)

    {

        path.push_back(x);

        x = fa[x];

    }

    path.push_back(s);

    for(int i = path.size()-;i >= ;i--)

        printf("%d ",path[i]);

    printf("%d\n",path[]);

}

void pre()

{

    cnt = ,tmp = ;

    memset(e,,sizeof(e));

    memset(ed,,sizeof(ed));

    memset(mrk,,sizeof(mrk));

    memset(head,,sizeof(head));

    memset(fa,,sizeof(fa));

}

int main()

{

    while(~scanf("%d%d",&n,&m))

    {

        pre();

        s = read(),t = read();

        for(int i = ; i <= m; i++)

        {

            e[i].x = read(),e[i].y = read();

            scanf("%lf%lf",&e[i].r,&e[i].d);

        }

        kruskal();

        dijkstra();

        printf("%.1lf %.1lf\n",dis[t],tmp);

    }

    return ;

}

注意：

题目稍稍有点坑

一定是先读入温度再读入长度

有几处double 打成 int

忽略了n 和 m

两个结构体的名搞混了

最最最坑：：：对换行符和空格的输出特别严格qwq（这谁抗的住w

（sdqxt莫得未来

巴特西

Travel in desert

题目大意

输入格式

输出格式

最新文章

热门文章