小伙伴出的题。
一眼看出是状压DP裸题。回忆poj2288 islands and bridges，然后就很好写了。
啪啪啪打了个状压DP出来(晚上寝室写的，其实是记忆化搜索)，发现sum总是INF
然后发现：printf函数调用的貌似不是运行solve之后的，而是还未运行solve时的值。
于是分开写就A了。
出题者跑了一秒多，貌似用的二分...反正不怎么看得懂。
果然DP大法吼哇！
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long LL;
using std::max;
using std::min;
const int N = ;
LL INF;
int n; LL f[ << N][N], sum[ << N][N], G[N][N]; void cal(int sta) {
int t[N];
for(int i = ; i < n; i++) {
t[i] = (sta >> i) & ;
}
for(int i = n - ; i >= ; i--) {
printf("%d", t[i]);
}
return;
} LL solve(int i, int j) { if(f[i][j] != INF) {
//printf("solve: ");
//cal(i);
//printf(" %d ans = %lld sum = %lld \n", j, f[i][j], sum[i][j]);
return f[i][j];
} int ct = ;
for(int ii = ; ii < n; ii++) {
ct += (i >> ii) & ;
}
if(ct < ) {
f[i][j] = INF - ;
return INF - ;
} LL ans = INF - , len = INF - ;
int sta = ((~( << j)) & i);
for(int ii = ; ii < n; ii++) {
if(!(G[ii][j] && ((i >> ii) & ))) {
continue;
}
LL t_ans = max(solve(sta, ii), G[ii][j]);
LL t_len = sum[sta][ii] + G[ii][j];
if(t_ans < ans) {
ans = t_ans;
len = t_len;
}
else if(ans == t_ans) {
len = min(len, t_len);
}
}
f[i][j] = ans;
sum[i][j] = len;
//printf("solve: ");
//cal(i);
//printf(" %d ans = %lld sum = %lld \n", j, ans, len);
return ans;
} int main() {
memset(f, 0x7f, sizeof(f));
memset(sum, 0x7f, sizeof(sum));
INF = sum[][]; int m, x, y;
LL R, z;
scanf("%d%d%lld", &n, &m, &R);
for(int i = ; i <= m; i++) {
scanf("%d%d%lld", &x, &y, &z);
x--; y--;
if(x == y || z > R) continue;
if(G[x][y]) z = min(z, G[x][y]);
G[x][y] = G[y][x] = z;
}
for(int i = ; i < n; i++) {
if(G[][i]) {
int sta = | ( << i);
f[sta][i] = G[][i];
sum[sta][i] = G[][i];
}
}
int ed = ( << n) - ;
LL ans = solve(ed, (n - ));
LL len = sum[ed][n - ];
if(ans >= INF - ) {
printf("wuwuwu~");
}
else {
printf("%lld %lld", ans, len);
}
return ;
}
AC代码