题解：【ABC291F】Teleporter and Closed off

标签：Teleporter const int 题解 static MAX off dir dis

题目链接

给定一个 \(n\) 个点的图，每个点只向编号最多大于它 \(m\) 的点连单向边，求不经过 \(2 \sim n\) 中的一个点，\(1 \to n\) 的最短路。注意到 \(m\) 很小，这里给出两种做法，都是基于 \(m\) 的特性来做的。

第一种是直接搜索。首先我们求出 \(1\) 到每个点的最短路和 \(n\) 到每个点的最短路。如果说不经过点 \(i\)，对于点 \(j\) 有 \(j+k>i (1 /le k /le m,j+k \le n)\) 且有边 \(j \to j+k\) 那就说明存在这条合法路径，直接枚举 \(j\) 和 \(k\) 即可，统计的答案即为 \(dis_{1 \to j} + dis_{j+k \to n} +1\)。

#include<bits/stdc++.h>
#define int long long
using namespace std;

namespace LgxTpre
{
	static const int MAX=100010;
	static const int INF=4557430888798830399;
	static const int mod=998244353;
	
	int n,m,ans;
	string s[MAX];
	
	struct edge
	{
		int nex,to;
	}e[MAX<<5];
	int head[MAX],cnt;
	inline void add(int x,int y)
	{
		e[++cnt].nex=head[x],head[x]=cnt,e[cnt].to=y;
		return;
	}
	
	queue<int> q;
	int dis[MAX][2];
	inline void bfs(int dir)
	{
		if(!dir) q.push(1),dis[1][0]=0;
		else q.push(n),dis[n][1]=0;
		while(!q.empty())
		{
			int now=q.front(); q.pop();
			for(int i=head[now];i;i=e[i].nex)
			{
				int to=e[i].to;
				if(dis[to][dir]>dis[now][dir]+1)
					dis[to][dir]=dis[now][dir]+1,q.push(to);
			}
		}
		return;
	}
	inline void init()
	{
		memset(head,0,sizeof head);
		cnt=0;
	}
	
	inline void lmy_forever()
	{
		cin>>n>>m;
		memset(dis,0x3f,sizeof dis);
		for(int i=1;i<=n;++i) cin>>s[i];
		for(int i=1;i<=n;++i)
			for(int j=1;j<=m;++j)
				if(s[i][j-1]=='1') 
					add(i,i+j);
		bfs(0);
		init();
		for(int i=1;i<=n;++i)
			for(int j=1;j<=m;++j)
				if(s[i][j-1]=='1') 
					add(i+j,i);
		bfs(1);
		for(int i=2;i<n;++i)
		{
			ans=INF;
			for(int j=max(1ll,i-m+1);j<i;++j)
				for(int k=1;k<=m;++k)
					if(j+k>i&&s[j][k-1]=='1')
						ans=min(ans,dis[j][0]+dis[j+k][1]+1);
			if(ans==INF) cout<<-1<<" ";
			else cout<<ans<<" ";
		}
		return;
	}
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	LgxTpre::lmy_forever();
	return (0-0);
}

第二种是矩阵。记 \(d_i\) 为 \(1 \to i\) 的最小花费，设计状态矩阵：

\[\begin{bmatrix} d_i \; d_{i-1} \; d_{i-2} \cdots d_{i-m} \end{bmatrix} \]

由于自带大常数的问题，我的矩阵相比于搜索处于极大的劣势。

#include<bits/stdc++.h>
#define int long long
using namespace std;

namespace LgxTpre
{
	static const int MAX=100010;
	static const int INF=4557430888798830399;
	static const int mod=998244353;
	
	int n,m,ans;
	string s[MAX];
	
	struct Matrix
	{
		static const int qck=15;
		int a[qck][qck];
		Matrix operator * (const Matrix& T) const 
		{
			Matrix res; memset(res.a,0x3f,sizeof res.a);
			for(int i=1;i<=m;++i)
				for(int j=1;j<=m;++j)
					for(int k=1;k<=m;++k)
						res.a[i][j]=min(res.a[i][j],a[i][k]+T.a[k][j]);
			return res;
		}
	}pre[MAX],suf[MAX],bas[MAX];;
	
	inline void lmy_forever()
	{
		cin>>n>>m;
		for(int i=1;i<=n;++i)
			cin>>s[i];
		for(int i=0;i<=n;++i)
			for(int j=1;j<=m;++j)
				for(int k=1;k<=m;++k)
					bas[i].a[j][k]=(k==j+1)?0:INF;	
		for(int i=1;i<=n;++i)
			for(int j=1;j<=m;++j)
				if(s[i][j-1]=='1')
					bas[i+j].a[j][1]=1;
		pre[2]=bas[2];
		for(int i=3;i<=n;++i) pre[i]=pre[i-1]*bas[i];
		suf[n]=bas[n];
		for(int i=n-1;i>=1;--i) suf[i]=bas[i]*suf[i+1];
		for(int i=2;i<n;++i)
		{
			if(i==2) ans=(bas[0]*suf[i+1]).a[1][1];
			else ans=(pre[i-1]*bas[0]*suf[i+1]).a[1][1];
			if(ans==INF) cout<<-1<<" ";
			else cout<<ans<<" ";
		}
		return;
	}
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	LgxTpre::lmy_forever();
	return (0-0);
}

标签：Teleporter,const,int,题解,static,MAX,off,dir,dis
From： https://www.cnblogs.com/LittleTwoawa/p/17158710.html