题意分析
$n$ 个点的完全图，求 $1\sim n$ 的最短路径。
如果我们直接使用朴素 Dijkstra $\mathcal O(n^2)$ 求解，会 $\text{TLE}$。
因此我们考虑优化建图。
优化建图
考虑到 $a_i,b_i<m$，因此边 $u\to v$ 的边权 $(a_u+b_v)\bmod m$ 只有可能是 $a_u+b_v$ 或 $a_u+b_v-m$。
AC 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
typedef pair<int,int> pr;
const int N=2e5;
struct node{
int a,b,id;
}a[3*N+1];
bool operator <(node a,node b){
return a.b<b.b;
}
struct edge{
int v,w,r;
}e[2*3*N+1];
int n,m,h[3*N+1];
priority_queue<pr,vector<pr>,greater<pr> > q;
void create(int u,int v,int w){
static int top;
e[++top]={v,w,h[u]};
h[u]=top;
}
int Dijkstra(int s,int t){
static bool vis[3*N+1];
static int dis[3*N+1];
memset(dis,0x3f,sizeof(dis));
dis[s]=0;
q.push({dis[s],s});
while(q.size()){
int u=q.top().second;
q.pop();
if(vis[u])continue;
vis[u]=true;
if(u==t)return dis[t];
for(int i=h[u];i>0;i=e[i].r){
if(vis[e[i].v])continue;
if(dis[e[i].v]>dis[u]+e[i].w){
dis[e[i].v]=dis[u]+e[i].w;
q.push({dis[e[i].v],e[i].v});
}
}
}
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i].a);
for(int i=1;i<=n;i++)scanf("%d",&a[i].b);
for(int i=1;i<=n;i++)a[i].id=i;
sort(a+1,a+n+1);
for(int i=1;i<=n;i++){
create(i+n,i,a[i].b);
create(i+2*n,i,0);
if(i>1)create(i+n,i+n-1,0);
if(i<n)create(i+n*2,i+n*2+1,a[i+1].b-a[i].b);
int pl=upper_bound(a+1,a+n+1,node{0,m-a[i].a-1,0})-a-1;
if(pl>=1)create(i,pl+n,a[i].a);
if(pl<n)create(i,pl+1+n*2,a[i].a+a[pl+1].b-m);
}int s,t;
for(int i=1;i<=n;i++){
if(a[i].id==1)s=i;
else if(a[i].id==n)t=i;
}printf("%d\n",Dijkstra(s,t));
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
