考虑 \(1\) 到其他关键城市的最短路的并是一棵以 \(1\) 为根的外向树，考虑在外向树上从叶子往根 dp。
设 \(f_{u, i, S}\) 为当前在点 \(u\)，已经翻修了 \(i\) 条道路，当前已经经过的关键点集合为 \(S\)，最短路最大值的最小值。
转移有两种情况，一种是在外向树上往父亲的边走，有 \(f_{v, i, S} \gets f_{u, i, S} + a, f_{v, i + 1, S} \gets f_{u, i, S} + b\)。
一种是在一个点把两棵子树合并，有 \(f_{u, i + j, S \cup T} \gets \max(f_{u, i, S}, f_{u, j, T})\)。朴素转移时间复杂度不能接受。因为 \(f_{u, i, S}\) 按 \(i\) 是单调不降的，考虑只用找到第一个 \(f_{u, j, T} \le f_{u, i, S}\) 即可转移。然后将 \(f_{u, i, S}\) 更新为 \(i\) 的前缀最小值即可。
code
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 110;
const int maxm = 260;
struct edg {
ll v, a, b;
edg(ll x = 0, ll y = 0, ll z = 0) : v(x), a(y), b(z) {}
};
ll n, m, K, id[maxn], f[maxn][maxn][maxm];
bool vis[maxn][maxn];
vector<edg> G[maxn];
struct node {
ll u, i, d;
node(ll a = 0, ll b = 0, ll c = 0) : u(a), i(b), d(c) {}
};
inline bool operator < (const node &a, const node &b) {
return a.d > b.d;
}
void solve() {
scanf("%lld%lld%lld", &n, &m, &K);
mems(f, 0x3f);
for (int i = 0, x; i < K; ++i) {
scanf("%d", &x);
f[x][0][1 << i] = 0;
}
for (int i = 1, u, v, a, b; i <= m; ++i) {
scanf("%d%d%d%d", &u, &v, &a, &b);
G[v].pb(u, a, b);
}
for (int S = 1; S < (1 << K); ++S) {
priority_queue<node> pq;
for (int u = 1; u <= n; ++u) {
for (int T = (S - 1) & S; T; T = (T - 1) & S) {
int U = S ^ T;
for (int i = 0, j = 0; i <= m; ++i) {
while (j < m && f[u][j][T] > f[u][i][U]) {
++j;
}
if (i + j <= m) {
f[u][i + j][S] = min(f[u][i + j][S], max(f[u][i][U], f[u][j][T]));
} else {
break;
}
}
}
for (int i = 1; i <= m; ++i) {
f[u][i][S] = min(f[u][i][S], f[u][i - 1][S]);
}
for (int i = 0; i <= m; ++i) {
if (f[u][i][S] < 1e9) {
pq.emplace(u, i, f[u][i][S]);
}
}
}
mems(vis, 0);
while (pq.size()) {
int u = pq.top().u, i = pq.top().i;
pq.pop();
if (vis[u][i]) {
continue;
}
vis[u][i] = 1;
for (edg e : G[u]) {
ll v = e.v, d1 = e.a, d2 = e.b;
if (f[v][i][S] > f[u][i][S] + d1) {
f[v][i][S] = f[u][i][S] + d1;
if (!vis[v][i]) {
pq.emplace(v, i, f[v][i][S]);
}
}
if (i < m && f[v][i + 1][S] > f[u][i][S] + d2) {
f[v][i + 1][S] = f[u][i][S] + d2;
if (!vis[v][i + 1]) {
pq.emplace(v, i + 1, f[v][i + 1][S]);
}
}
}
}
}
for (int i = 0; i <= m; ++i) {
printf("%lld ", f[1][i][(1 << K) - 1]);
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}