USACO09JAN Safe Travel

将最短路径树建出来后就等于是要求将每个点的父边断开后的最短路径。将这条边断开后树会分成两半,此时的最短路径一定是先从 $1$ 到原有树上的某一个节点,再从一条不在树上的边到达另一棵树,然后走最短路到达终点,若这条边为 $(u,v,w)$ 则最短路径可表示为 $dist[u]+dist[v]+w-dist[x]$,可以发现前面三项只跟边有关,所以将每条边按照这个值排序,从小到大更新。考虑每条边能影响到的点只有 $u,v$ 到 $lca(u,v)$ 路径上的点(不包括 $lca(u,v)$),每次先暴力跳更新答案,然后用并查集将所有被更新过的点缩起来。总复杂度为 $\mathcal O(n \times \log_2 n)$。

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>

const int MAXN = 1e5;
const int MAXM = 2e5;
const int INF = 0x3f3f3f3f;

int n, m, edge;
int father[MAXN | 1], fset[MAXN | 1], fst[MAXN | 1], dist[MAXN | 1], ans[MAXN | 1], depth[MAXN | 1];
bool vis[MAXN | 1];

struct Heap {
  int x, dis;
  Heap() : x(0), dis(0) {}
  Heap(int a, int b) : x(a), dis(b) {}
  friend bool operator< (const Heap &lhs, const Heap &rhs) {
    return lhs.dis > rhs.dis;
  }
};

struct Edge {
  int to, w, nxt;
  Edge() : to(0), w(0), nxt(0) {}
  Edge(int a, int b, int c) : to(b), w(c), nxt(fst[a]) {}
} e[MAXM << 1 | 1];

struct EE {
  int x, y, z;
  EE() : x(0), y(0), z(0) {}
  EE(int a, int b, int c) : x(a), y(b), z(c) {}
  friend bool operator< (const EE &lhs, const EE &rhs) {
    return dist[lhs.x] + dist[lhs.y] + lhs.z < dist[rhs.x] + dist[rhs.y] + rhs.z;
  }
} ee[MAXM | 1];

inline int read() {
  register int x = 0;
  register char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x;
}

inline void addEdge(int a, int b, int c) {
  e[++edge] = Edge(a, b, c);
  fst[a] = edge;
}

void Dijkstra() {
  std::priority_queue < Heap > q;
  q.push(Heap(1, 0));
  memset(dist, INF, sizeof(dist));
  dist[1] = 0;
  do {
    Heap from = q.top();
    q.pop();
    if (dist[from.x] != from.dis) continue;
    for (int k = fst[from.x]; k; k = e[k].nxt) {
      int to = e[k].to, w = e[k].w;
      if (dist[to] > dist[from.x] + w) {
        dist[to] = dist[from.x] + w;
        q.push(Heap(to, dist[to]));
      }
    }
  } while (!q.empty());
  std::queue < int > qq;
  qq.push(1);
  do {
    int from = qq.front();
    qq.pop();
    for (int k = fst[from]; k; k = e[k].nxt) {
      int to = e[k].to, w = e[k].w;
      if (dist[to] == dist[from] + w && !depth[to]) {
        depth[to] = depth[from] + 1;
        father[to] = from;
        qq.push(to);
      }
    }
  } while (!qq.empty());
}

int find(int x) {
  return fset[x] == x ? x : fset[x] = find(fset[x]);
}

int main() {
  n = read();
  m = read();
  for (int i = 1; i <= m; ++i) {
    int a = read(), b = read(), c = read();
    addEdge(a, b, c);
    addEdge(b, a, c);
    ee[i].x = a;
    ee[i].y = b;
    ee[i].z = c;
  }
  Dijkstra();
  std::sort(ee + 1, ee + m + 1);
  for (int i = 1; i <= n; ++i) fset[i] = i;
  memset(ans, -1, sizeof(ans));
  for (int i = 1; i <= m; ++i) {
    int u = ee[i].x, v = ee[i].y, w = ee[i].z + dist[u] + dist[v];
    if (father[u] == v || father[v] == u) continue;
    int son = -1;
    while (u != v) {
      if (depth[u] < depth[v]) std::swap(u, v);
      if (!vis[find(u)]) {
        vis[find(u)] = 1;
        ans[u] = w - dist[u];
        if (son != -1) fset[find(son)] = find(u);
        son = u;
      }
      u = father[find(u)];
    }
  }
  for (int i = 2; i <= n; ++i) printf("%d\n", ans[i]);
  return 0;
}
最后修改:2019 年 08 月 12 日 02 : 58 PM

发表评论