最短路 #状压dp #滚动优化 #POI #Year2007
从前 \(k\) 个跑 \(dijksta\) ,对这 \(k\) 个点到达的状态状压
会 MLE
,考虑每次转移都只会增加一个状压下的 \(1\) ,按照 \(popcount\) 分组做滚动
// Author: xiaruize
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
const int N = 2e5 + 10;
int n, m, k;
vector<pii> g[50050];
int dis[25][50050];
int st[50050];
int cnt[1050000], id[1050000];
vector<int> vec[23];
int dp[190000][2][23];
void dijkstra(int x)
{
mms(dis[x], 0x3f);
dis[x][x] = 0;
priority_queue<pii, vector<pii>, greater<pii>> q;
q.push({0, x});
while (!q.empty())
{
auto [ds, u] = q.top();
q.pop();
if (ds != dis[x][u])
continue;
for (auto [v, w] : g[u])
{
if (dis[x][v] > dis[x][u] + w)
{
dis[x][v] = dis[x][u] + w;
q.push({dis[x][v], v});
}
}
}
}
void solve()
{
cin >> n >> m >> k;
k++;
rep(i, 1, m)
{
int u, v, w;
cin >> u >> v >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
rep(i, 1, k) dijkstra(i);
cin >> m;
rep(i, 1, m)
{
int u, v;
cin >> u >> v;
st[v] |= (1 << u - 2);
}
rep(i, 2, k) st[i] |= (1 << i - 2);
if (k == 1)
{
cout << dis[1][n] << endl;
return;
}
rep(msk, 1, (1 << k - 1) - 1)
{
int t = __builtin_popcount(msk);
vec[t].push_back(msk);
cnt[t]++;
id[msk] = cnt[t];
}
int res = INF;
rep(i, 1, k - 1)
{
for (auto v : vec[i])
{
mms(dp[id[v]][i & 1], 0x3f);
rep(cur, 2, k)
{
if ((st[cur] | v) != v)
continue;
if (v - (v & -v) != 0)
{
rep(x, 2, k)
{
if (x != cur && (v & (1 << x - 2)))
dp[id[v]][i & 1][cur] = min(dp[id[v]][i & 1][cur], dp[id[v ^ (1 << cur - 2)]][(i & 1) ^ 1][x] + dis[x][cur]);
}
}
else
dp[id[v]][i & 1][cur] = dis[1][cur];
if (v == (1 << k - 1) - 1)
{
res = min(res, dp[id[v]][i & 1][cur] + dis[cur][n]);
}
}
}
}
cout << res << endl;
}
#ifndef ONLINE_JUDGE
bool end_of_memory_use;
#endif
signed main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int testcase = 1;
// cin >> testcase;
while (testcase--)
solve();
#ifndef ONLINE_JUDGE
cerr << "Memory use:" << (&end_of_memory_use - &start_of_memory_use) / 1024.0 / 1024.0 << "MiB" << endl;
cerr << "Time use:" << (double)clock() / CLOCKS_PER_SEC * 1000.0 << "ms" << endl;
#endif
return 0;
}
标签:Tourist,int,Attractions,POI2007ATR,状压,cin,push,rep,dis
From: https://www.cnblogs.com/xiaruize/p/18136788