Stavo provando a risolvere il problema e sono arrivato ad una soluzione che potrebbe farmi ottenere 75 punti solo che va in TLE in qualche testcase eppure mi sembra tutto corretto a livello di complessità.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<ll> dijkstra(int N, vector<vector<pair<ll, ll>>> &adj, ll start)
{
vector<ll> dist(N, 1e18);
dist[start] = 0;
queue<pair<ll, ll>> pq;
pq.push({start, 0});
while (!pq.empty())
{
auto [node, d] = pq.front();
pq.pop();
if (d > dist[node]) continue;
for (auto [next, w] : adj[node])
{
if (dist[node] + w < dist[next])
{
dist[next] = dist[node] + w;
pq.push({next, -dist[next]});
}
}
}
return dist;
}
vector<ll> shorten(int N, int M, int Q, vector<ll> K, vector<int> A, vector<int> B, vector<int> C)
{
vector<vector<pair<ll, ll>>> adj(N);
for (int i = 0; i < M; i++)
{
adj[A[i]].push_back({B[i], C[i]});
adj[B[i]].push_back({A[i], C[i]});
}
// From point 0, 1 ,2 find minimum distance to all other points
vector<ll> dist0 = dijkstra(N, adj, 0);
vector<ll> dist1 = dijkstra(N, adj, 1);
vector<ll> dist2 = dijkstra(N, adj, 2);
// Min paths are dist0 + 2*dist1 + dist2
vector<pair<ll, ll>> paths;
for (int i = 0; i < N; i++)
paths.push_back({dist0[i] + 2 * dist1[i] + dist2[i], dist1[i]});
vector<ll> sol(Q, 1e18);
for (int i = 0; i < Q; i++)
{
for (int j = 0; j < N; j++)
{
sol[i] = min(sol[i], max(paths[j].first - K[i] - min(paths[j].second, K[i]), 0LL));
}
}
return sol;
}