[JZOJ5818] 【NOIP提高A组模拟2018.8.15】做运动

Description

一天，Y 君在测量体重的时候惊讶的发现，由于常年坐在电脑前认真学习，她的体重有了突飞猛进的增长。
幸好 Y 君现在退役了，她有大量的时间来做运动，她决定每天从教学楼跑到食堂来减肥。
Y 君将学校中的所有地点编号为 1 到 n，其中她的教学楼被编号为 S，她的食堂被编号为 T，学校中有 m 条连接两个点的双向道路，保证从任意一个点可以通过道路到达学校中的所有点。
然而 Y 君不得不面临一个严峻的问题，就是天气十分炎热，如果 Y 君太热了，她就会中暑。于是 Y 君调查了学校中每条路的温度 t，及通过一条路所需的时间 c。Y 君在温度为 t 的地方跑单位时间，就会使她的热量增加 t。
由于热量过高 Y 君就会中暑，而且 Y 君也希望在温度较低的路上跑，她希望在经过的所有道路中最高温度最低的前提下，使她到达食堂时的热量最低 (从教学楼出发时，Y 君的热量为 0)。
请你帮助 Y 君设计从教学楼到食堂的路线，以满足她的要求。你只需输出你设计的路线中所有道路的最高温度和 Y 君到达食堂时的热量。

Input

第一行由一个空格隔开的两个正整数 n, m，代表学校中的地点数和道路数。
接下来 m 行，每行由一个空格隔开的四个整数 a, b, t, c 分别代表双向道路的两个端点，温度和通过所需时间.
最后一行由一个空格隔开的两个正整数 S, T，代表教学楼和食堂的编号。
注意：输入数据量巨大，请使用快速的读入方式。

Output

一行由一个空格隔开的两个整数，分别代表最高温度和热量。

Sample Input

Sample Output

3 24

Data Constraint

10% 的数据满足 t = 0
另外 10% 的数据满足 c = 0
另外 30% 的数据满足 n ≤ 2000
100% 的数据满足 n ≤ 5 × 10^5 , m ≤ 10^6 , 0 ≤ t ≤ 10000, 0 ≤ c ≤ 10^8 , 1 ≤ a, b, S, T ≤ n, S ≠ T

把边权从小到大排序，然后一个个加入，用并查集维护连通性，如果S和T联通就退出，第一个答案求出。

然后加入所有边权小于第一个答案的边，跑spfa求出S到T的最短路。

话说今天A组的题比B组简单多了。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

using namespace std;

#define int long long

inline int read() {

    int res=;char ch=getchar();

    while(!isdigit(ch)) ch=getchar();

    while(isdigit(ch)) res=(res<<)+(res<<)+(ch^),ch=getchar();

    return res;

}

#define reg register

#define N 500005

#define M 1000005

int n, m, S, T;

struct edge {

    int nxt, to, val, tim, from;

}ed[M*], ed2[M*];

int head[N], cnt;

inline void add(int x, int y, int z, int w)

{

    ed[++cnt] = (edge) {head[x], y, z, w, x};

    head[x] = cnt;

}

inline void ADD(int x, int y, int z, int w)

{

    ed2[++cnt] = (edge) {head[x], y, z, w, x};

    head[x] = cnt;

}

inline bool cmp(edge a, edge b)

{

    return a.val < b.val;

}

bool can[M*];

int fa[N];

int Find(int x) {return x==fa[x]?x:fa[x]=Find(fa[x]);}

int ans;

int dis[N];

bool ex[N];

inline void spfa()

{

    memset(dis, 0x3f, sizeof dis);

    memset(ex, , sizeof ex);

    queue <int> q;

    q.push(S);

    dis[S] = ;

    while(!q.empty())

    {

        int x = q.front();q.pop();

        ex[x] = ;

        for (reg int i = head[x] ; i ; i = ed2[i].nxt)

        {

            int to = ed2[i].to;

            if (dis[to] > dis[x] + ed2[i].tim * ed2[i].val)

            {

                dis[to] = dis[x] + ed2[i].tim * ed2[i].val;

                if (!ex[to]) ex[to] = , q.push(to);

            }

        }

    }

}

signed main()

{

    freopen("running.in", "r", stdin);

    freopen("running.out", "w", stdout);

    n = read(), m = read();

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

    {

        int x = read(), y = read(), z = read(), w = read();

        add(x, y, z, w);

    }

    S = read(), T = read();

    sort (ed + , ed +  + cnt, cmp);

    for (reg int i =  ; i <= n ; i ++) fa[i] = i;

    for (reg int i =  ; i <= cnt ; i ++)

    {

        int x = ed[i].from, y = ed[i].to;

        int fx = Find(x), fy = Find(y);

        if (fx == fy) continue;

        fa[fx] = fy;

        if (Find(S) == Find(T)) {ans = ed[i].val; break;}

    }

    int tot = cnt, cnt = ;

    memset(head, , sizeof head);

    for (reg int i =  ; i <= tot ; i ++)

        if (ed[i].val <= ans) ADD(ed[i].from, ed[i].to, ed[i].val, ed[i].tim), ADD(ed[i].to, ed[i].from, ed[i].val, ed[i].tim);

    spfa();

    printf("%lld %lld\n", ans, dis[T]);

    return ;

}

Sample