记录编号	601114	评测结果	AAAAAAAAAAAA
题目名称	3109.[GXOI/GZOI2019]旅行者	最终得分	100
用户昵称	LikableP	是否通过	通过
代码语言	C++	运行时间	13.420 s
提交时间	2025-06-02 17:15:27	内存使用	28.55 MiB

#include <cstdio>
#include <cstring>
#include <queue>
#define isdigit(ch) (ch >= '0' && ch <= '9')
typedef long long ll;

template <typename T>
T read() {
  T res = 0, f = 1;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ 48);
  return res * f;
}

template <typename T>
void write(T x, char ed = '\n') {
  if (x < 0) putchar('-'), x = -x;
  static int sta[64], top;
  do {
    sta[++top] = x % 10;
    x /= 10;
  } while(x);
  while (top) {
    putchar(sta[top--] ^ 48);
  }
  putchar(ed);
}

template <typename T>
T min(T x, T y) {
  return x < y ? x : y;
}

const int MAXN = 1e5 + 10;
const int MAXM = 5e5 + 10;

struct Star {
  struct EDGE {
    int v, w, next;
  } edge[MAXM << 1];
  int head[MAXN], edgeNum;
  void AddEdge(int u, int v, int w) {
    edge[++edgeNum].v = v;
    edge[edgeNum].w = w;
    edge[edgeNum].next = head[u];
    head[u] = edgeNum;
  }
} orign, _new;

int s, t;
ll ans;
ll dis[MAXN];
bool vis[MAXN];
ll Dijkstra() {
  memset(dis, 0x3f, sizeof dis);
  memset(vis, 0, sizeof vis);
  ::std::priority_queue <::std::pair <ll, int>> q;
  dis[s] = 0;
  q.push(::std::make_pair(0, s));
  while (!q.empty()) {
    int u = q.top().second; q.pop();
    if (vis[u]) continue;
    vis[u] = 1;
    for (int i = _new.head[u]; i; i = _new.edge[i].next) {
      int v = _new.edge[i].v, w = _new.edge[i].w;
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        q.push(::std::make_pair(-dis[v], v));
      }
    }
  }
  return dis[t];
}

int T;
int like[MAXN];

int main() {
  freopen("WAW.in", "r", stdin);
  freopen("WAW.out", "w", stdout);
  T = read<int>();
  while (T--) {
    memset(orign.edge, 0, sizeof orign.edge);
    memset(orign.head, 0, sizeof orign.head);
    orign.edgeNum = 0;
    int n = read<int>(), m = read<int>(), k = read<int>();
    for (int i = 1; i <= m; ++i) {
      int u = read<int>(), v = read<int>(), w = read<int>();
      orign.AddEdge(u, v, w);
    }
    for (int i = 1; i <= k; ++i) {
      like[i] = read<int>();
    }
    s = n + 1, t = n + 2;
    ans = 0x7fffffffffffffff;
    for (int i = 0; (1 << i) <= k; ++i) {
      _new = orign;
      for (int j = 1; j <= k; ++j) if (j & (1 << i)) {
        _new.AddEdge(s, like[j], 0);
        //printf("Connect s with %d\n", like[j]);
      } else {
        _new.AddEdge(like[j], t, 0);
        //printf("Connect %d with t\n", like[j]);
      }
      //printf("#####################\n");
      ans = min(ans, Dijkstra());
      _new = orign;
      for (int j = 1; j <= k; ++j) if (j & (1 << i)) {
        _new.AddEdge(like[j], t, 0);
        //printf("Connect s with %d\n", like[j]);
      } else {
        _new.AddEdge(s, like[j], 0);
        //printf("Connect %d with t\n", like[j]);
      }
      ans = min(ans, Dijkstra());
      //printf("---------------------\n");
    }
    printf("%lld\n", ans);
  }
  return 0;
}