Problem - G - Codeforces

題目大意：給出一長度為n的二進制字符串s，和m對二進制字符串e1和e2，，費用為d，s和一對字符串操作后s中是1且e1中也是1的位置會變成0，s中是0，e2中是1的位置會變成1，得到新的s，每對字符串可以操作任意次，問能否使s變成全0字符串

1<=n<=10;1<=m<=1000；1<=d<=1000

思路：可以發(fā)現(xiàn)s和一對字符串操作，就相當于s&(~e1)|e2（可以用真值表推導），因為字符串的位數(shù)最高是10位，也就是說無論怎么操作，最多出現(xiàn)1024個不同的字符串，所以我們可以把每個不同的字符串當做一個節(jié)點，先用bitset把字符串都轉化為數(shù)字，然后每一對字符串作為邊，用set來做bfs的隊列，從起點開始，將set中的每個點都用上面的到的公式與每對字符串進行操作，如果到新的的距離小于之前記錄的距離，就更新這個最短距離，最后隊列為空后輸出到0點的距離即可

//#include<__msvc_all_public_headers.hpp>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3 + 5;
ll n, m;
pair<ll, pair<ll, ll>>e[N];
ll dis[5000];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t--)
	{
		cin >> n >> m;
		bitset<10>sx;
		cin >> sx;
		ll s = sx.to_ullong();//將二進制字符串轉化為long long型數(shù)據(jù)
		for (int i = 1; i <= m; i++)
		{
			ll dx;
			bitset<10>ux, vx;
			cin >> dx >> ux >> vx;
			ll u = ux.to_ullong();
			ll v = vx.to_ullong();
			e[i].first = dx;
			e[i].second = make_pair(u, v);//記錄每對字符串的費用，和e1，e2對應的數(shù)字
		}
		for (int i = 0; i <= (1 << (n + 1)); i++)
		{//初始化每個點到起點的距離
			dis[i] = 0x7fffffff;
		}
		dis[s] = 0;
		set<pair<ll, ll>>q = { make_pair(0, s) };//用集合記錄創(chuàng)造出的點，及到其的最短距離，避免重復
		while (!q.empty())
		{
			pair <ll, ll> temp = *q.begin();
			q.erase(q.begin());//set彈出堆頂元素的方法
			ll d = temp.first;
			ll u = temp.second;
			for (int i = 1; i <= m; i++)
			{
				ll v = u & (~e[i].second.first) | e[i].second.second;//得到新的點
				if (dis[v] > d + e[i].first)
				{
					q.erase(make_pair(dis[v], v));//更新距離要把原先記錄的刪掉
					dis[v] = d + e[i].first;
					q.insert(make_pair(dis[v], v));
				}
			}
		}
		if (dis[0] == 0x7fffffff)
		{//到終點的距離沒更新，就是沒通路
			cout << -1 << endl;
		}
		else
		{
			cout <<dis[0] << endl;
		}
	}
	return 0;
}

? 文章來源地址http://www.zghlxwxcb.cn/news/detail-548640.html

?

到了這里，關于G. Rudolf and CodeVid-23 codeforces1846G的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！