首页 > 其他分享 >POI2007ATR-Tourist Attractions

POI2007ATR-Tourist Attractions

时间:2024-04-15 19:49:25浏览次数:25  
标签:Tourist int Attractions POI2007ATR 状压 cin push rep dis

最短路 #状压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

相关文章

  • [POI2007] [LUOGU P3451]旅游景点 Tourist Attractions
    本题解由于作者太菜在POI及LUOGU上会TLE,该题解主要讲思路,剩下的内存优化请各位大佬自行补充,欢迎评论区讨论本题解运行时间10406ms,空间194584KiB题目描述FGD想从成都去上海旅游。在旅途中他希望经过一些城市并在那里欣赏风景,品尝风味小吃或者做其他的有趣的事情。经过这些城......
  • 旅游景点 Tourist Attractions
    [POI2007]ATR-TouristAttractions题目背景FGD想从成都去上海旅游。在旅途中他希望经过一些城市并在那里欣赏风景,品尝风味小吃或者做其他的有趣的事情。经过这些城市的顺序不是完全随意的,比如说FGD不希望在刚吃过一顿大餐之后立刻去下一个城市登山,而是希望去另外什么地方喝下......
  • 旅游景点 Tourist Attractions (壮压 DP)题解
    简化题意题目链接——不卡内存班题目链接——卡内存版给定\(n\)个点和\(m\)条边组成的无向图,按照一定限制要求停留\(2\simk+1\)共\(k\)个点(可以经过但不停留),求最短的从\(1\)出发到\(n\)的路径长。限制情况如下:共有\(q\)个限制,接下来\(q\)行,每行两个数\(x......
  • 旅游景点 Tourist Attractions
    目录题目链接题目描述题意概括思路历程1.找最短路2.设计状态代码实现题目链接题目描述题目描述FGD想从成都去上海旅游。在旅途中他希望经过一些城市并在那里欣赏风景,品尝风味小吃或者做其他的有趣的事情。经过这些城市的顺序不是完全随意的,比如说FGD不希望在刚吃过一顿大餐之......
  • GYM 101147K Touristic Trip
    首先可以看出这是一个条件概率\(P(A/B)=\frac{P(AB)}{P(B)}\),其中\(A\)事件为“满足在\(Z\)城市时寄出第\(Q\)张明信片”,\(B\)事件为“满足得到的明信片序列与给出的明信片序列相同”那只需要求出\(P(AB)\)和\(P(B)\)就能得到最终答案了首先考虑\(B\)事件发现......
  • 【题解】CF487E Tourists / 圆方树
    概念圆方树是一种基于无向图构造的树。我们知道,圆方树最早是WC上提出的处理仙人掌的东西,用于将树上做法拓展到复杂度正确的仙人掌做法。但是一些关于点双有性质的题也......
  • CF487E Tourists
    题意给定一张无向图,点有点权。每次可以修改一个点的点权,或者询问从\(a\)到\(b\)所有不经过重复点的路径上最小的点权是多少。Solution考虑一个点双,点双中任意两个点......
  • CF487E Tourists(Tarjan,圆方树,树链剖分,线段树)
    CF487ETourists带权无向图\(N,M\),\(Q\)次询问\(s,t\)所有不经过重复点可能路径经过的最小值的最小值。CODE每次修改一个圆点\(u\)周围的方点有点难。可是李神......