Solução por Pedro Racchetti
Conhecimentos utilizados:
Para esse problema, primeiro precisamos notar que podemos usar o algoritmo de Dijkstra, para encontrar o menor caminho de cada cidade até qualquer posto de gasolina guardaremos esse número no vetor 
. Além disso, guardamos para cada cidade, qual é o posto mais perto.
Podemos então, para cada estrada, perceber que o menor caminho que passa por ela tem tamanho ![dist[x] + dist[y] + d](https://i0.wp.com/noic.com.br/wp-content/plugins/latex/cache/tex_f9ad3bb1d985e3865292155c349c33e6.gif?w=640&ssl=1)
. Podemos então ordenar os caminhões e as estradas no mesmo vetor, utilizando o valor encontrado para as estradas e 
para os caminhões. Isso nos garante que quando chegarmos a um caminhão, todos os caminhos de um posto para outro com tamanho menor ou igual à já terão sido analisados.
Porém, como analisamos uma aresta? podemos conectar o posto mais perto da cidade 
com o posto mais perto da cidade 
no Union-Find, e para os caminhões, basta verificar se as duas extremidades das arestas estão na mesma componente!
Segue o código comentado, para melhor compreensão:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include<bits/stdc++.h> | |
| using namespace std; | |
| const int MAXN = 2e5 + 10; | |
| typedef long long ll; | |
| const ll INF = 1e18; | |
| ll dist[MAXN]; | |
| int deonde[MAXN]; | |
| //Guardamos os caminhos e caminhões na mesma estrutura | |
| struct query{ | |
| int v1, v2, id, tipo; | |
| ll d; | |
| query(int _v1 = 0, int _v2 = 0, int _id = 0, int _tipo = 0, ll _d = 0){ | |
| v1 = _v1; | |
| v2 = _v2; | |
| id = _id; | |
| tipo = _tipo; | |
| d = _d; | |
| } | |
| bool operator < (query q)const{ | |
| if(d == q.d) return tipo < q.tipo; | |
| return d < q.d; | |
| } | |
| }; | |
| vector<query> v; | |
| bool ans[MAXN], eposto[MAXN], marc[MAXN]; | |
| vector<pair<int, ll > > grafo[MAXN]; | |
| int n, m, s; | |
| //usamos o union-find com compressão de caminho | |
| int pai[MAXN], altura[MAXN]; | |
| int find(int x){ | |
| if(pai[x] == x) return x; | |
| return pai[x] = find(pai[x]); | |
| } | |
| void join(int u, int v){ | |
| u = find(u); | |
| v = find(v); | |
| if(u == v) return; | |
| if(altura[u] < altura[v] ) pai[u] = v; | |
| else if(altura[u] > altura[v] ) pai[v] = u; | |
| else{ | |
| pai[u] = v; | |
| altura[v]++; | |
| } | |
| } | |
| void dijkstra(){ | |
| set<pair<ll, int> > q; | |
| for(int i = 1; i <= n; i++){ | |
| if(eposto[i]){ | |
| //iniciamos a pilha do dijkstra com todos os postos, e distancia zero | |
| deonde[i] = i; | |
| q.insert(make_pair(0, i)); | |
| }else{ | |
| dist[i] = INF; | |
| } | |
| } | |
| while(!q.empty()){ | |
| int v = q.begin() -> second; | |
| q.erase(q.begin()); | |
| if(marc[v]) continue; | |
| marc[v] = 1; | |
| for(int i = 0; i < grafo[v].size(); i++){ | |
| int viz = grafo[v][i].first; | |
| int p = grafo[v][i].second; | |
| if(dist[viz] > dist[v] + p){ | |
| dist[viz] = dist[v] + p; | |
| deonde[viz] = deonde[v]; | |
| // marcamos o posto mais perto, e a distancia até ele | |
| q.insert(make_pair(dist[viz], viz)); | |
| } | |
| } | |
| } | |
| for(int i = 0; i < m; i++){ | |
| //calculamos o tamanho do caminho que passsa em cada aresta | |
| v[i].d += dist[v[i].v1] + dist[v[i].v2]; | |
| } | |
| } | |
| int main(){ | |
| scanf("%d %d %d", &n, &s, &m); | |
| for(int i = 0; i < s; i++){ | |
| int u; | |
| scanf("%d", &u); | |
| eposto[u] = 1; | |
| } | |
| for(int i = 0; i < m; i++){ | |
| int x, y; | |
| ll d; | |
| scanf("%d %d %lld", &x, &y, &d); | |
| grafo[x].push_back(make_pair(y, d)); | |
| grafo[y].push_back(make_pair(x, d)); | |
| query q = query(x, y, i, 0, d); | |
| v.push_back(q); | |
| //inicializamos o grafo e as arestas | |
| } | |
| dijkstra(); | |
| for(int i = 1; i <= n; i++) pai[i] = i, altura[i] = 0; | |
| int k; | |
| scanf("%d", &k); | |
| for(int i = 0; i < k; i++){ | |
| int a, b; | |
| ll c; | |
| scanf("%d %d %lld", &a, &b, &c); | |
| query q = query(a,b,i,1,c); | |
| v.push_back(q); | |
| } | |
| sort(v.begin(), v.end()); | |
| for(int i = 0; i < v.size(); i++){ | |
| if(v[i].tipo == 0){ | |
| //caso o elemento seja uma qareste, conectamos os dois postos | |
| join(deonde[v[i].v1], deonde[v[i].v2]); | |
| }else{ | |
| //caso o elemento seja um caminhao, verificamos se eles estao na mesma componente | |
| if(find(deonde[v[i].v1]) != find(v[i].v2) ) ans[v[i].id] = false; | |
| else ans[v[i].id] = true; | |
| } | |
| } | |
| for(int i = 0; i < k; i++){ | |
| if(ans[i]) printf("TAK\n"); | |
| else printf("NIE\n"); | |
| } | |
| } |