#C240302B. B-01串

前言（Front talk)

标签本来应该是最短路算法，由于这道题的转换思想更重要，因此归为”思维“一类。

网址（Website）

题目详情 - B-01串 - Super

题解 - B-01串 - Super

题解（Solution）

将每次反转操作转化为前缀翻转，初始的串也可以转化为和两个操作（假设原来的串都是）。

最终要使这些操作进行后所有的操作抵消，原来的串就会全部变为一了。

对于翻转，我们可以知道：若要使操作失效，我们可以先翻转，再翻转，容易发现这个性质很像边的性质，所以直接以和建边，边权为，直接跑个最短路就好了。

代码（Code）

#include<bits/stdc++.h>
#include<vector>
#include<queue>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
inline int input(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9+7;
const int N = 501234;

int a,b,c,d,e,m,ans;
int s1,s2,t1,t2;
vector<P> ft[N];

bitset<N> vst;
int dis[5][N];
void dijkstra(int st,int p){
	priority_queue<P> q;q.emplace(0,st);
	memset(dis[p],0x3f,sizeof dis[p]);
	vst.reset(),dis[p][st]=0;
	while(q.size()){
		int x=q.top().second;q.pop();
		if(vst[x]) continue;
		vst[x]=true;
		for(auto pp:ft[x]){
			int y=pp.first,v=pp.second;
			if(dis[p][y]>dis[p][x]+v){
				dis[p][y] = dis[p][x]+v;
				q.emplace(-dis[p][y],y);
			}
		}
	}
}

signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	string str("b");
	freopen((str+".in").c_str(),"r",stdin);
	freopen((str+".out").c_str(),"w",stdout);
	cin>>a>>b>>c>>d>>e>>m;int Tim = clock();
	For(i,1,m){
		int x=input(),y=input()+1;
		ft[x].emplace_back(y,y-x);
		ft[y].emplace_back(x,y-x);
	}int aa=a+1,bb=a+b+1,cc=a+b+c+1,dd=a+b+c+d+1;
	dijkstra(aa,1),dijkstra(bb,2),dijkstra(cc,3);
	ans = min({dis[1][bb]+dis[3][dd],dis[1][cc]+dis[2][dd],dis[1][dd]+dis[2][cc]});
	cout<<(ans>=inf?-1:ans)<<'\n';
	return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}