链接：https://www.luogu.com.cn/problem/AT_abc232_g
暴力的做法肯定不行，这道题要用到一个比较经典的拆点操作：把一个点拆成内点和外点。在接下来的分析中会慢慢介绍。
由于题目每次连的边都是单向边，那要考虑的问题是：比如说现在要从1走到3，怎么走才能与暴力建边等价。
先不考虑取模这个条件。假如说我一开始就是暴力建边，那么比如从1走到3的路径长度就是(a[1]+b[3])。那么我们可以把一个点拆成一个内点和外点，其中外点向内点链接一条长度为0的边，内点向外点链接一条 b[1]+a[i] 的边，然后外点向下一个外点链接一条 b[i+1]-b[i] 的边。
为什么要这么连呢？我们考虑题目中要求的是求1到n的最短路。那么从1号点出发时，先是从内点走向外点，随后一直走外点直到目的地，对应的边权该抵消的抵消该相加的相加。到最后达到目的地的时候，累加起来的结果就是我们想要的边权。比如说从1走到3，那么路径上的所有边权 就是 b[1]+a[1]+b[2]-b[1]+b[3]-b[2]+0=a[1]+b[3]
现在再来考虑取模这个条件。我们观察数据范围可以发现 a[i]+b[i] 不可能超过 2*m ，那么也就是说可以直接把取模这个条件转化成 (a[i]+b[i]-m). 我们可以将b数组先进行排序，从小到大与进行连边。我们二分查找出第一个需要取模操作的点 k，连一条从i的内点指向k的外点的一条长度为 (b[k]-a[i]-m) 的边即可。
因为这个k相当于一个分界点，在这个分界点只需要出现一次 -m，在后面的累加过程中这个 -m 是不会被消掉的，其他的累加抵消操作和上面一致。
连好了边，跑一次Dijkstra即可。理解不了，可以画一张图，然后看一看是怎么抵消的就行。然后要理解Dij跑最短路的原理就会知道到这个点到答案怎么更新，然后就可以分析每条边有一种各司其职的感觉，从内点到外点的边有些在更新答案的时候是没有用的，不会影响到最短路统计。
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int,int> PII;
#define mp make_pair
#define ull unsigned long long
#define all(x) x.begin(), x.end()
//__builtin_count()
typedef array<int,2> pr;
const unsigned int mask = (chrono::steady_clock::now().time_since_epoch().count());
inline int gcd(int a, int b){return b == 0 ? a : gcd(b, a % b);}//gcd(a,b)=gcd(a,b-a)(b>a);
inline int lcm(int a, int b){return a / gcd(a, b) * b;}//lcm(n,m)=n*m/gcd(n,m)
const ll mod = 998244353;
const int inv2 = (mod+1)/2;
#define lson rt<<1
#define rson rt<<1|1
int addmod(int &x, int y) {x = (x + y >= mod ? x + y - mod : x + y);return 1;}
ll qpow(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll inv(int x){return qpow(x,mod-2);}
inline void read(__int128 &x)
{
char c; while(!((c=getchar())>='0'&&c<='9'));
x=c-'0';
while((c=getchar())>='0'&&c<='9') (x*=10)+=c-'0';
}
int o[200010],on;
inline void output(__int128 x)
{
on=0;
while(x) o[++on]=x%10,x/=10;
for(int i=on;i>=1;i--) cout<<o[i];
}
const int maxn = 5e5+10;
struct node{
int a,b,id;
bool operator < (const node &k) const{
return b<k.b;
}
}a[maxn];
struct dian{
int v,w;
bool operator < (const dian &k) const{
return w>k.w;
}
}g[maxn];
int n,m;
int b[maxn],dis[maxn],vis[maxn];
vector<pr> vec[maxn];
void dij(int st)
{
priority_queue<dian> que;
memset(dis,0x3f,sizeof(dis));
que.push({st,dis[st]});
dis[st]=0;
while(!que.empty())
{
auto x=que.top();
que.pop();
if(vis[x.v]) continue;
vis[x.v]=1;
for(auto to:vec[x.v])
{
if(dis[to[0]]>dis[x.v]+to[1])
{
dis[to[0]]=dis[x.v]+to[1];
que.push({to[0],dis[to[0]]});
}
}
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i].a;
a[i].id=i;
}
for(int i=1;i<=n;i++)
{
cin>>a[i].b;
}
sort(a+1,a+1+n);
for(int i=1;i<=n;i++)
{
b[i]=a[i].b;
}
int st,ed;
for(int i=1;i<=n;i++)
{
if(a[i].id==1)
{
st=i;
}
else if(a[i].id==n) ed=i;
vec[i+n].push_back({i,0});
vec[i].push_back({n+1,b[1]+a[i].a});
int k=lower_bound(b+1,b+1+n,m-a[i].a)-b;
if(k<=n)
{
vec[i].push_back({k+n,b[k]+a[i].a-m});
}
}
for(int i=1;i<n;i++)
{
vec[i+n].push_back({i+n+1,b[i+1]-b[i]});
}
dij(st);
cout<<dis[ed]<<'\n';
return 0;
}