# Recover Path

## 题目描述

Traveller Gregory is famous for his ability to always choose the shortest path for his journey. Ostap is a journalist who seeks for information about the recent Gregory’s trip. He managed to get the evidence that during this trip Gregory visited a number of cities. However, there is no information about the order in which they were visited, and no information about the starting city and the ending city of Gregory’s trip (the entire trip is (one of) the shortest path between these cities). Help Ostap to find any shortest path that contains all specified cities.
Country in which Gregory traveled consists of $n$ cities and $m$ undirected roads between them. For each road Ostap knows the time it takes to travel it, and the “shortest” word above is with respect to those times.
It is guaranteed that there exists some shortest path going through all specified cities.

## 代码

#include <algorithm>
#include <cstdio>
#include <cstring>

static int const N = 100005;
int ne = 1, top, h[N], d[N], que[N], id[N], lst[N], pre[N], ans[N];
bool in[N], v[N];
struct Edge {
int u, v, w, nxt;
} e[N << 1];

void add_edge(int u, int v, int w) {
e[++ne] = (Edge){u, v, w, h[u]}, h[u] = ne;
e[++ne] = (Edge){v, u, w, h[v]}, h[v] = ne;
}

void spfa(int s) {
int qb = 0, qe = 1;
memset(d, 0x3f, sizeof d), d[s] = 0, que[0] = s, in[s] = 1;
for (; qb != qe;) {
int u = que[qb++];
in[u] = 0, qb == N && (qb = 0);
for (int i = h[u]; i; i = e[i].nxt)
if (d[e[i].v] > d[u] + e[i].w) {
d[e[i].v] = d[u] + e[i].w;
if (!in[e[i].v]) {
if (qb == qe || d[e[i].v] > d[que[qb]])
que[qe++] = e[i].v, in[e[i].v] = 1, qe == N && (qe = 0);
else
!~--qb && (qb = N - 1), que[qb] = e[i].v, in[e[i].v] = 1;
}
}
}
}

int main() {
int n, m, k, t;
scanf("%d%d", &n, &m);
for (int i = 1, u, v, w; i <= m; ++i)
scanf("%d%d%d", &u, &v, &w), add_edge(u, v, w);
scanf("%d%d", &k, &t), v[t] = 1, spfa(t);
int s = t;
for (int i = 2; i <= k; ++i)
scanf("%d", &t), v[t] = 1, d[s] < d[t] && (s = t);
spfa(s);
for (int i = 1; i <= n; ++i)
id[i] = i;
std::sort(id + 1, id + n + 1, [&](int const &i, int const &j) { return d[i] < d[j]; });
for (int i : id) {
lst[i] += v[i];
for (int j = h[i]; j; j = e[j].nxt)
if (d[e[j].v] == d[i] + e[j].w && lst[e[j].v] < lst[i])
lst[e[j].v] = lst[i], pre[e[j].v] = j;
}
for (int i = 1; i <= n; ++i)
if (lst[i] == k) {
for (int j = pre[i]; j; j = pre[e[j].u])
ans[top++] = j >> 1;
break;
}
printf("%d\n", top);
for (int i = 0; i < top; ++i)
printf("%d ", ans[i]);
puts("");
return 0;
}


418 I'm a teapot