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 $$dist$$. 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$$. Podemos então ordenar os caminhões e as estradas no mesmo vetor, utilizando o valor encontrado para as estradas e $$c_i$$ 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 à $$c_i$$ já terão sido analisados.
Porém, como analisamos uma aresta? podemos conectar o posto mais perto da cidade $$x$$ com o posto mais perto da cidade $$y$$ 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:
| #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"); | |
| } | |
| } |
