Codeforces 1343E

One and a half hours passed from reading this problem to writing the solution.

The task is to reassign edge prices so that the cost of travelling a -> b -> c is minimised.

I had no idea at first.

I kept thinking about recording edges, but keeping them in shortest paths is too expensive. Instead, change the source vertex and compute three distance arrays. This is a common trick in many problems.

Then enumerate the middle vertex. That was the step I did not think of.

struct edge {
  int to, cost;
};

vector<int> dijkstra(const vector<vector<edge>> &g, int s) {
  vector<int> d(g.size() + 5, INF);
  priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> que;
  d[s] = 0;
  que.emplace(0, s);
  while (!que.empty()) {
    auto p = que.top();
    que.pop();
    int u = p.second;
    if (d[u] < p.first) continue;
    for (auto &e : g[u]) {
      int v = e.to;
      if (d[v] > d[u] + e.cost) {
        d[v] = d[u] + e.cost;
        que.emplace(d[v], v);
      }
    }
  }
  return d;
}

ll n,m,a,b,c;
ll p[maxn];
vector<vector<edge>> g;
void solve() {
    SLLA(n);
    SLLA(m);
    SLLA(a);
    SLLA(b);
    SLLA(c);
    g.resize(n+5);
    REPP(i,1,n) {
        g[i].clear();
    }
    REPP(i,1,m) {
        SLLA(p[i]);
    }
    sort(p+1,p+m+1);
    REPP(i,1,m) {
        p[i] += p[i-1];
    }
    REPP(i,1,m) {
        int h,f;
        SA(h);
        SA(f);
        g[h].push_back(edge{f, 1});
        g[f].push_back(edge{h, 1});
    }

    std::vector<int> dis1 = dijkstra(g, a);
    std::vector<int> dis2 = dijkstra(g, b);
    std::vector<int> dis3 = dijkstra(g, c);
    ll ans = LL_INF;
    REPP(i,1,n) {
        if(dis1[i] + dis2[i] + dis3[i] > m) {
            continue;
        }
        ans = min(ans, p[dis1[i] + dis2[i] + dis3[i]] + p[dis2[i]]);
    }
    printf("%lld\n", ans);
}