GXOI/GZOI2019-lvxingzhe

暴力：

对于每个特殊点为起始点计算Dijkstra或spfa。。

然而这样有很多重复操作，很多路径会被重复走。

改善：

考虑把特殊点分组，分组只计算两组间的最短路，组内不计算。显然，分为两组最优（如果分为多组的话其实和没有分组一样会走重复路径）。最方便的分组方法就是把特殊点编号转为二进制，第$i$次分组，将第$i$位为$1$的分一组，其余另一组。共需分$\log n$次组。

为获得每一次分组的最短路，我们利用类似于网络流建图的方法。将$s$连向一组的所有点无向边，边权为$0$，将另一组的所有点连向$t$无向边，边权为$0$，$s$到$t$的最短路和$t$到$s$的最短路的最小值就是这一次分组的最短路结果。最终结果为所有分组最短路的最小值。

---

#include <bits/stdc++.h>
#define memset0(x, s) memset(x, 0, sizeof(int) * (s + 2))
#define next                                                                   \
  ___________________________________________________________________________________________________
using namespace std;

typedef long long ll;
const int MAXN = 100005, MAXM = 500005;
const ll INF = 1ll << 60;

struct Edge {
  int u, to, next;
  ll w;
} edge[MAXM << 1];

struct node {
  int id;
  ll dis;
  node(int tid, ll tdis) {
    id = tid;
    dis = tdis;
  }
  bool operator<(const node &B) const { return dis > B.dis; }
};

ll dis1[MAXN], dis2[MAXN], ans;
int head1[MAXN], head2[MAXN], id[MAXN], from1[MAXN], from2[MAXN], n, m, k, tot;
bool vis[MAXN];

inline void addedge1(int u, int v, ll w) {
  edge[++tot] = (Edge){u, v, head1[u], w}, head1[u] = tot;
}

inline void addedge2(int u, int v, ll w) {
  edge[++tot] = (Edge){u, v, head2[u], w}, head2[u] = tot;
}

void dij1() {
  priority_queue<node> q;
  while (!q.empty())
    q.pop();
  for (int i = 1; i <= n; i++)
    dis1[i] = INF, vis[i] = 0;
  for (int i = 1; i <= k; i++)
    dis1[id[i]] = 0ll, from1[id[i]] = id[i], q.push(node(id[i], 0ll));
  while (!q.empty()) {
    node cur = q.top();
    q.pop();
    int u = cur.id;
    if (vis[u])
      continue;
    vis[u] = 1;
    for (int e = head1[u]; e; e = edge[e].next) {
      int v = edge[e].to;
      if (dis1[v] > dis1[u] + edge[e].w)
        dis1[v] = dis1[u] + edge[e].w, from1[v] = from1[u],
        q.push(node(v, dis1[v]));
    }
  }
}

void dij2() {
  priority_queue<node> q;
  while (!q.empty())
    q.pop();
  for (int i = 1; i <= n; i++)
    dis2[i] = INF, vis[i] = 0;
  for (int i = 1; i <= k; i++)
    dis2[id[i]] = 0ll, from2[id[i]] = id[i], q.push(node(id[i], 0ll));
  while (!q.empty()) {
    node cur = q.top();
    q.pop();
    int u = cur.id;
    if (vis[u])
      continue;
    vis[u] = 1;
    for (int e = head2[u]; e; e = edge[e].next) {
      int v = edge[e].to;
      if (dis2[v] > dis2[u] + edge[e].w)
        dis2[v] = dis2[u] + edge[e].w, from2[v] = from2[u],
        q.push(node(v, dis2[v]));
    }
  }
}

int main() {
  int T;
  scanf("%d", &T);
  for (; T; --T) {
    memset0(head1, n), memset0(head2, n), memset0(edge, m << 1),
        tot = 0, ans = INF, scanf("%d%d%d", &n, &m, &k);
    ll w;
    for (int i = 1, u, v; i <= m; i++)
      scanf("%d%d%lld", &u, &v, &w), addedge1(u, v, w), addedge2(v, u, w);
    for (int i = 1; i <= k; i++)
      scanf("%d", id + i);
    dij1(), dij2();
    for (int i = 1; i <= m << 1; i += 2) {
      int u = edge[i].u, v = edge[i].to;
      ll w = edge[i].w;
      if (from1[u] != from2[v])
        ans = min(ans, dis1[u] + w + dis2[v]);
    }
    printf("%lld\n", ans);
  }
  return 0;
}