思路

如果朴素建图的话，有 $n^2$ 条边，显然不可行，考虑如何优化这个建图的过程。

首先由于 $a_i,b_i<m$ ，对于 $u\rightarrow v$ 的一条边，边权只可能是 $a_u+b_v$ 或 $a_u+b_v-m$，前者当 $b_v<m-a_u$ 时取到，后者当 $b_v\ge m - a_u$ 时取到。

首先考虑 $m$ 很小的情况，我们对 $0\sim m-1$ 建立 $m$ 个辅助节点 $W_0\sim W_{m-1}$， $W_i$ 向 $W_{(i+1)\ {\rm{mod}} \ m}$ 连权值为 $1$ 的边，不难发现， $W_{m-a_u}$ 沿着环走到 $W_{b_v}$ 点所经过的距离恰好是 $(a_u + b_v)\ {\rm{mod}}\ m$ ，这是由于 $(a_u+b_v)\ {\rm{mod}}\ m=(b_v-(m-a_u))\ {\rm{mod}}\ m$，而后者与 $W_{m-a_u}$ 沿着环走到 $W_{b_v}$ 点所经过的距离相等，此时我们再对$u\rightarrow W_{m-{a_u}}, W_{b_u}\rightarrow u$ 分别连权值为 $0$ 的边，在这个新图上 $1\sim n$ 的最短路就等于原图上的 $1\sim n$ 的最短路。

但 $m$ 的范围是很大的，我们要想办法缩减辅助节点的数量，一个关键点在于，对于点 $W_i$ 和点 $W_j$，如果 $W_i$ 到 $W_j$ 之间只有唯一一条路径的话，便可以将这条路径缩成一条长度和路径长度相同的边，以此来做到边的数量的缩减。我们将所有的 $m-{a_u}$ 以及 $b_u$ 进行离散化，将这些点按照从小到大连成一个环，再按照上述的做法建图，便可以建出一个点数、边数都是 $O(n)$ 数量级的图，准确的说，点数的上限为 $3n$，边数的上限为 $4n$，在这个图上以 $1$ 为源点跑最短路即可解决问题，时间复杂度为 $O(n\log n)$ 。

参考代码

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>

using namespace std;
using i64 = long long;

const int MAXN = 600005; 
const i64 INF = 1e18;

struct Edge 
{
	int v, w; 
};

vector<Edge> e[MAXN]; 
i64 dis[MAXN];
bool vis[MAXN];

struct Point 
{
	int p;
	i64 w;
};

struct cmp 
{
	bool operator()(Point &a, Point &b)
	{
		return a.w > b.w;
	}
};


int find(const vector<int>& v, int x) 
{
	return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}

int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, m;
	cin >> n >> m;
	
	vector<int> a(n + 1), b(n + 1);
	vector<int> v; 
	
	for (int i = 1; i <= n; i++) 
	{
		cin >> a[i];
		v.push_back(m - a[i]);
	}
	
	for (int i = 1; i <= n; i++) 
	{
		cin >> b[i]; 
		v.push_back(b[i]);
	}
	

	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	

	for (int i = 1; i <= n; i++) 
	{
		e[i].push_back(Edge{find(v, m - a[i]) + n, 0}); 
		e[find(v, b[i]) + n].push_back(Edge{i, 0}); 
	}
	
	int t = v.size();
	
	for (int i = 0; i < t; i++)
	{
		int dist = (v[(i + 1) % t] - v[i] + m) % m;
		int cur = i + n + 1, ne = (i == t - 1) ? n + 1 : cur + 1;
		e[cur].push_back(Edge{ne, dist});
	}

	fill(dis, dis + 3 * n + 1, INF);
	priority_queue<Point, vector<Point>, cmp> q; 
	q.push(Point{1, 0});
	dis[1] = 0;
	
	for (int t = 1; t <= n + v.size(); t++)
	{
		Point head = q.top();
		while (vis[head.p])
		{
			q.pop();
			head = q.top();
		}
		int now = head.p;
		vis[now] = true;
		for (int i = 0; i < e[now].size(); i++)
		{
			int v = e[now][i].v;
			int w = e[now][i].w;
			if (dis[now] + w < dis[v])
			{
				dis[v] = dis[now] + w;
				q.push((Point){v, dis[v]});
			}
		}
	}
	
	cout << dis[n] << '\n';
	return 0;
}