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

Problem

【AMPPZ2014】Petrol

Description

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

Input

第一行包含三个正整数(,)，表示点数、加油站数和边数。
第二行包含个互不相同的正整数，表示每个加油站。
接下来行，每行三个正整数,,(,,)，表示和之间有一条长度为的双向边。
接下来一行包含一个正整数()，表示询问数。
接下来行，每行包含三个正整数(,,)，表示一个询问。

Output

输出行。第行输出第个询问的答案，如果可行，则输出，否则输出。

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

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

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;
}