Teleportation
鲍勃最近访问了一个奇怪的传送系统。该系统包含 \(n\) 个房间，编号为 \(0\) 到 \(n-1\)。每个房间都安装了一个传送设备。每个传送设备都有一个看起来像钟表表面的仪表板，上面有一个指针，显示数字 \(0\) 到 \(n-1\)，按顺时针顺序排列。最初，第 \(i\) 个房间的传送设备上的指针指向数字 \(a_i\)。
当鲍勃在房间 \(i\)（\(0 \leq i \leq n-1\)）时，他可以进行以下操作任意次数：
- 传送：立即传送到房间 \((i + a_i) \mod n\)。
- 逆时针移动指针。设置 \(a_i \leftarrow a_i + 1\)。
每次操作需要一个时间单位。鲍勃从房间 \(0\) 开始，他想尽快到达某个房间 \(x\)。他想知道需要多长时间。
\(Input\)
输入的第一行包含两个整数 \(n\)（\(2 \leq n \leq 10^5\)）和 \(x\)（\(1 \leq x \leq n - 1\)），分别表示房间的数量和鲍勃的目的地房间。
下一行包含 \(n\) 个整数 \(a_0, a_1, \ldots, a_{n-1}\)（\(0 \leq a_i \leq n - 1\)），其中 \(a_i\)（\(0 \leq i \leq n - 1\)）表示第 \(i\) 个房间的指针指向的数字。
\(Output\)
输出一个整数，表示鲍勃从房间 0 到达房间 \(x\) 所需的最短时间。
\(Sample1\)
4 3
0 1 2 3
4
\(Sample2\)
4 3
0 0 0 0
4
\(Sample3\)
4 3
2 2 2 2
2
思路：这题得转换一下，不然边要建太多了，不妨设1到n-1为本,n到\(2*n-1\)为真，对于本来讲，从1到n-1做有向边，从左指向右边（注意n-1->0也要），设立边费用为1；且对于每个数建立个零费用边到其对应的真边
随后就是i+a[i]了，建立对应i的真边i+n到(i+a[i])%n的本的单向边，且设立费用为1.
随后优先队列走一个最短路就行了，从n出发
从真点集出发一是可以直接到对应连接的本点，二是可以利用本点集中单向边的指向性质，一个有向环，实现费用转移优化。
这样子既合理有实现了边集大小的控制，即3*n,最后走一遍迪杰斯特拉就可得到答案
由于迪杰斯特拉本质就是最近扩散，所以当遇以目标点扩散时，其一定为最小值，这时可以直接break
#include<iostream>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<cmath>
#include<string>
#define ll long long
#define lowbit(x) (x & -x)
#define endl "\n"
using namespace std;
vector<pair<ll,ll>>g[250000];
void fio()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
bool vis[250000];
ll n,m;
ll ans=0;
void bfs()
{
priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>>q;
q.push({0,n});
while(!q.empty())
{
ll x=q.top().first;
ll y=q.top().second;
q.pop();
if(vis[y])
continue;
vis[y]=1;
if(y==m+n)
{
ans=x;
break;
}
for(auto j:g[y])
{
q.push({x+j.first,j.second});
}
}
}
int main()
{
fio();
cin>>n>>m;
for(ll i=0;i<n;i++)
{
ll x;
cin>>x;
g[n+i].push_back({1,(x+i)%n});
}
for(ll i=0;i<n-1;i++)
{
g[i].push_back({1,i+1});
g[i].push_back({0,i+n});
}
g[n-1].push_back({1,0});
g[n-1].push_back({0,2*n-1});
bfs();
cout<<ans<<endl;
}