BZOJ4144【AMPPZ2014】Petrol < 最短路+MST >

Problem

【AMPPZ2014】Petrol

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;256\;MB}$

Description

给定一个$n$个点、$m$条边的带权无向图，其中有$s$个点是加油站。
每辆车都有一个油量上限$b$，即每次行走距离不能超过$b$，但在加油站可以补满。
$q$次询问，每次给出$x,y,b$，表示出发点是$x$，终点是$y$，油量上限为$b$，且保证$x$点和$y$点都是加油站，请回答能否从$x$走到$y$。

Input

第一行包含三个正整数$n,s,m$($2\le s\le n\le 2\times 10^5$,$1\le m\le 2\times 10^5$)，表示点数、加油站数和边数。
第二行包含$s$个互不相同的正整数$c[1],c[2],...c[s]\;(1\le c[i]\le n)$，表示每个加油站。
接下来$m$行，每行三个正整数$u[i]$,$v[i]$,$d[i]$($1\le u[i],v[i]\le n$,$u[i]\ne v[i]$,$1\le d[i]\le 10^5$)，表示$u[i]$和$v[i]$之间有一条长度为$d[i]$的双向边。
接下来一行包含一个正整数$q$($1\le q\le 2\times 10^5$)，表示询问数。
接下来$q$行，每行包含三个正整数$x[i],y[i],b[i]$($1\le x[i],y[i]\le n$,$x[i]\ne y[i]$,$1\le b[i]\le 2\times 10^9$)，表示一个询问。

Output

输出$q$行。第$i$行输出第$i$个询问的答案，如果可行，则输出$\mathrm{TAK}$，否则输出$\mathrm{NIE}$。

Sample Input

6 4 5
1 5 2 6
1 3 1
2 3 2
3 4 3
4 5 5
6 4 5
4
1 2 4
2 6 9
1 5 9
6 5 8

Sample Output

TAK
TAK
TAK
NIE

标签：最短路 MST

Solution

一道精妙的$\mathrm{MST}$题。
首先考虑走到一个点，先去离它最近的加油站，回来后再去下一个点肯定比直接去要优。
于是用多源最短路预处理出每个点到它最近的加油站的距离，随后给每一条边分别加上它的起点和终点离它们最近加油站的距离。
对于询问，先离线下来按$b$值排序，按照边权加入边，用并查集维护。对于每个询问，先将比它的$b$值小的所有边都加入，再询问起点和终点是否联通即可。

Code

#include <bits/stdc++.h>
#define fir first
#define sec second
#define mp make_pair
#define pii pair<int,int>
#define MAX_N 200000
using namespace std;
int n, m, s, c[MAX_N+5], fa[MAX_N+5], dis[MAX_N+5];    vector <pii> G[MAX_N+5];
struct edge {int u, v, c;    bool operator < (const edge &t) const {return c < t.c;}} E[MAX_N+5];
struct query {int id, u, v, c;    bool operator < (const query &t) const {return c < t.c;}} Q[MAX_N+5];
int getf(int x) {return fa[x] == x ? x : fa[x] = getf(fa[x]);}
void Dijkstra() {
    priority_queue <pii> que;	bool mrk[MAX_N+5];
    memset(dis, 0x7f, sizeof dis), memset(mrk, false, sizeof mrk);
    for (int i = 1; i <= s; i++)	dis[c[i]] = 0, que.push(mp(-dis[c[i]], c[i]));
    while (!que.empty()) {
        int u = que.top().sec;	que.pop();
        if (mrk[u])	continue;	mrk[u] = true;
        for (int i = 0; i < (int)G[u].size(); i++) {
            int v = G[u][i].fir, w = G[u][i].sec;
            if (dis[u]+w < dis[v])	dis[v] = dis[u]+w, que.push(mp(-dis[v], v));
        }
    }
}
int main() {
    scanf("%d%d%d", &n, &s, &m);	for (int i = 1; i <= s; i++) scanf("%d", c+i);
    for (int i = 1; i <= m; i++)	scanf("%d%d%d", &E[i].u, &E[i].v, &E[i].c), G[E[i].u].push_back(mp(E[i].v, E[i].c)), G[E[i].v].push_back(mp(E[i].u, E[i].c));
    Dijkstra();		for (int i = 1; i <= m; i++)	E[i].c += dis[E[i].u]+dis[E[i].v];
    int q;	scanf("%d", &q);	for (int i = 1; i <= q; i++)	Q[i].id = i, scanf("%d%d%d", &Q[i].u, &Q[i].v, &Q[i].c);
    sort(E+1, E+m+1), sort(Q+1, Q+q+1);		for (int i = 1; i <= n; i++)	fa[i] = i;		bool ans[MAX_N+5];
    for (int i = 1, j = 1; i <= q; i++) {
        for (int u, v; j <= m && E[j].c <= Q[i].c; j++)
            if ((u = getf(E[j].u)) != (v = getf(E[j].v)))	fa[u] = v;
        ans[Q[i].id] = getf(Q[i].u) == getf(Q[i].v);
    }
    for (int i = 1; i <= q; i++)	puts(ans[i] ? "TAK" : "NIE");
    return 0;
}