HDU 6166 Senior Pan

官方题解：

比赛的时候用错误算法过了。。。来补一波正解。
正解好屌。

代码：

#include<bits/stdc++.h>
using namespace std;#define fi first
#define se second
#define pb push_back
typedef long long LL;
typedef pair<int, int> PII;const int N = 1e5+10;
const LL INF = 1e18;bool inq[N];
int b[N];
LL d[N];
vector<PII> G[N];LL spfa(int s, int t) {for(int i = 1; i <= t; i++) d[i] = INF, inq[i] = 0;d[s] = 0;queue<int> Q; Q.push(s);while(!Q.empty()) {int u = Q.front(); Q.pop();inq[u] = 0;for(PII x:G[u]) {int v = x.fi, w = x.se;if(d[v] > d[u]+x.se) {d[v] = d[u]+x.se;if(!inq[v]) inq[v] = 1, Q.push(v);}}}return d[t];
}LL solve(int k, int s, int t, int op) {LL ans = INF;for(int i = 0; i <= 20; i++) {int x = 1<<i;if(x >= k) break;for(int j = 0; j < k; j++) {if((x&j) == op) G[s].pb({b[j], 0});else G[b[j]].pb({t, 0});}ans = min(ans, spfa(s, t));G[s].clear();for(int j = 0; j < k; j++) {if((x&j) != op) G[b[j]].pop_back();}}return ans;
}int main() {int T;scanf("%d", &T);while(T--) {int n, m, k;scanf("%d%d", &n, &m);for(int i = 1; i <= n+2; i++) G[i].clear();while(m--) {int u, v, w;scanf("%d%d%d", &u, &v, &w);G[u].pb({v, w});}scanf("%d", &k);for(int i = 0; i < k; i++) scanf("%d", &b[i]);static int cas = 0;LL ans = (solve(k, n+1, n+2, 1), solve(k, n+1, n+2, 0));printf("Case #%d: %lld\n", ++cas, ans);}return 0;
}