Problem Statement
We have a directed graph with $N$ vertices, called Vertex $1$, Vertex $2$, $\ldots$, Vertex $N$.
For each pair of integers such that $1 \leq i, j \leq N$ and $i \neq j$, there is a directed edge from Vertex $i$ to Vertex $j$ of weight $(A_i + B_j) \bmod M$. (Here, $x \bmod y$ denotes the remainder when $x$ is divided by $y$.)
There is no edge other than the above.
Print the shortest distance from Vertex $1$ to Vertex $N$, that is, the minimum possible total weight of the edges in a path from Vertex $1$ to Vertex $N$.
Constraints
- $2 \leq N \leq 2 \times 10^5$
- $2 \leq M \leq 10^9$
- $0 \leq A_i, B_j < M$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$ $M$ $A_1$ $A_2$ $\ldots$ $A_N$ $B_1$ $B_2$ $\ldots$ $B_N$
Output
Print the minimum possible total weight of the edges in a path from Vertex $1$ to Vertex $N$.
Sample Input 1
4 12 10 11 6 0 8 7 4 1
Sample Output 1
3
Below, $i \rightarrow j$ denotes the directed edge from Vertex $i$ to Vertex $j$.
Let us consider the path $1$ $\rightarrow$ $3$ $\rightarrow$ $2$ $\rightarrow$ $4$.
- Edge $1\rightarrow 3$ weighs $(A_1 + B_3) \bmod M = (10 + 4) \bmod 12 = 2$,
- Edge $3 \rightarrow 2$ weighs $(A_3 + B_2) \bmod M = (6 + 7) \bmod 12 = 1$,
- Edge $2\rightarrow 4$ weighs $(A_2 + B_4) \bmod M = (11 + 1) \bmod 12 = 0$.
Thus, the total weight of the edges in this path is $2 + 1 + 0 = 3$.
This is the minimum possible sum for a path from Vertex $1$ to Vertex $N$.
Sample Input 2
10 1000 785 934 671 520 794 168 586 667 411 332 363 763 40 425 524 311 139 875 548 198
Sample Output 2
462
一道优化建图题.
观察到这里的取模最多只会减一次，所以与其说是取模，不如说当 \(a_i+b_j\ge m\) 时，代价减去 \(m\)。
先看如果没有取模，怎么做。一个经典的拆点，把一个点拆成内点和外点，外点向内点连代价为 \(b_i\) 的边，内点向外点连 \(a_i\) 的边。然后随便用0边把外点连起来。
但这样很明显不好扩展。注意到一件事，如果 \(a_i+b_j\ge m\)，将点按照 \(b\) 排序后，\(k>j\) 的点的代价都要减去 \(m\)。所以将所有点按照 \(b\) 排序，然后仍然拆成内点和外点，外点从点 \(i\) 连向 \(i+1\),代价 \(b_{i+1}-b_i\)。内外点之间连 0 边。这个构图非常巧妙，如果从点 \(i\) 的内点向某一个点连了一条边权为 \(a_i+b_j-m\) 的边，这个内点到达任何一个 \(k>j\)，都相当于有一条边权为 \(a_i+b_k-m\) 的边。对于一个内点，他先朝 \(1\) 的外点连一条边权为 \(a_i+b_1\) 的边，在二分出第一个 \(a_i+b_j\ge m\) 的点，连一条边权为 \(a_i+b_j-m\) 的边，就可以达到题目中的效果。
但这样好像有些点同时连了 \(a_i+b_j\) 和 \(a_i+b_j-m\) 的边？但其实不影响答案。因为题目求最短路。
所有的边权为正，可以跑dij.
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=4e5+5;
int n,b[N],e_num,m,u,v,hd[N],vis[N];
LL dis[N];
struct node{
int a,b,id;
bool operator<(const node&n)const{
return b<n.b;
}
}a[N];
struct edge{
int v,nxt,w;
}e[N<<3];
struct dian{
int v;
LL w;
bool operator<(const dian&d)const{
return w>d.w;
}
};
priority_queue<dian>q;
void add_edge(int u,int v,int w)
{
// printf("%d %d %d\n",u,v,w);
e[++e_num]=(edge){v,hd[u],w};
hd[u]=e_num;
}
void dijkstra(int s)
{
q.push((dian){s,0});
memset(dis,0x7f,sizeof(dis));
dis[s]=0;
while(!q.empty())
{
int k=q.top().v;
q.pop();
if(vis[k])
continue;
vis[k]=1;
for(int i=hd[k];i;i=e[i].nxt)
{
if(dis[e[i].v]>dis[k]+e[i].w)
{
dis[e[i].v]=dis[k]+e[i].w;
q.push((dian){e[i].v,dis[e[i].v]});
}
}
}
}
int main()
{
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),a[i].id=i;
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)
b[i]=a[i].b;
for(int i=1;i<=n;i++)
{
// b[i]=a[i].b;
if(a[i].id==1)
u=i;
else if(a[i].id==n)
v=i;
add_edge(i+n,i,0);
add_edge(i,n+1,b[1]+a[i].a);
int k=lower_bound(b+1,b+n+1,m-a[i].a)-b;
// printf("%d %d\n",k,a[i].a);
if(k<=n)
add_edge(i,k+n,a[i].a+b[k]-m);
}
// printf("%d %d\n",u,v);
for(int i=1;i<n;i++)
add_edge(i+n,i+n+1,b[i+1]-b[i]);
dijkstra(u);
// for(int i=1;i<=n+n;i++)
// printf("%lld ",dis[i]);
printf("%lld",dis[v]);
return 0;
}