Siemka ponownie, tym razem mam kłopot z zadaniem Przemytnicy z X OI, I etap. Od razu zauważyłem, że w tym zadaniu trzeba wykorzystać algorytm Dijkstry. Oto moje spostrzeżenia nt. tego zadania:
Zauważyłem, że można oprócz tablicy dis[x], (która przechowuje min. odległość od wierzchołka 1. do x) zrobić tablicę disTo1[x], która przechowywać będzie min. odległość z wierzchołka x do 1 (o ile istnieje).
Tutaj załączam tabelkę, która zwizualizuje wam ten problem i zadanie stanie się proste do zrozumienia: link. Suma sum jest równa sumie dis[x], disTo1[x] oraz połowy val[x], gdyż cło wynosi połowę przewożonego ładunku.
Jedyny problem dla mnie to jakiś wydajny sposób na stworzenie tablicy disTo1[x]. Ma ktoś pomysł i zechciałby się nim podzielić? I jak to zrobić tak, aby nie lecieć n (gdzie n to liczba wierzchołków) razy algorytmem Dijkstry?
Jak do tej pory napisałem tyle:
[on-line]
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
vector <pair <int, int>> v[5001];
priority_queue <pair <int, int>> q;
int dis[5001], disTo1[5001], val[5001], sum[5001];
bool vis[5001];
const int INF = 1e9 + 1;
int n;
void dij(int w) {
for (int i = 2; i <= n; i ++)
dis[i] = INF;
dis[1] = 0;
q.push({0, w});
while (!q.empty()) {
w = q.top().y;
q.pop();
if (vis[w])
continue;
vis[w] = 1;
for (auto a : v[w]) {
dis[a.x] = min(dis[a.x], dis[w] + a.y);
if (!vis[a.x])
q.push({-dis[a.x], a.x});
}
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; i ++)
cin >> val[i];
int k;
cin >> k;
while (k --) {
int a, b, c;
cin >> a >> b >> c;
v[a].push_back({b, c});
}
dij(1);
/* for (int i = 1; i <= n; i ++)
cout << i << ' ' << dis[i] << '\n'; */
}
