你正在筹划一场城市定向。你拥有一张包含 $n$ 个地点的城市地图，其中编号为 1 的为起点。地图上标明了所有选手能够通行的道路的信息，这样的道路一共有 $m$ 条，分为两种类型：
- 普通道路。对于每条普通道路，地图上都会给出它连接的两个地点的编号 $u$, $v$，以及选手通过它需要花费的时间 $w$。每条普通道路在任意时刻都可以双向通行。
- 地铁线路。对于每条地铁线路，地图上都会给出它连接的两个相邻的站点编号 $u$, $v$，始发时刻 $t_0$, 运行时间间隔 $t$，以及从站点 $u$ 出发抵达站点 $v$ 所需的时间 $w$。注意，地铁的运行时间间隔为 $t$ 代表只有在 $t_0, t_0+t, t_0+2t, t_0+3t, ...$ 时刻会有地铁进站，在地铁进站时刻 $t'$ 及以前到达站点 $u$ 的选手都能够在 $t'$ 时刻搭乘上地铁，上地铁所花费的时间忽略不计。
现在，筹备组的你为了规划合适的线路，需要为任意一个地点 $i$ 计算出：0 时刻从起点出发，到达地点 $i$ 的最早时刻。
输入
第一行包含两个正整数 $n,m$。分别表示地点个数和道路条数。
接下来 $m$ 行。每行描述一条道路。
道路的描述有两种格式：
0 u v w：普通道路，$u,v,w$ 的含义同题目描述。1 u v t0 t w：地铁线路，$u,v,t_0,t,w$ 的含义同题目描述。
保证 $1 \le u,v \le n$， 保证从起点出发能到达所有的地点。
输出
一行 $n$ 个数，第 $i$ 个数表示在 0 时刻从起点出发，到达地点 $i$ 的最早时刻。
输入样例1
4 6
1 1 2 1 5 1
1 2 3 4 2 1
0 1 4 5
1 1 4 2 5 1
0 4 2 5
0 4 1 1输出样例1
0 2 5 1输入样例2
5 20
0 1 2 35
0 1 5 27
1 5 4 13 9 26
1 4 3 3 13 35
0 3 1 3
0 4 2 13
1 1 1 2 3 11
1 3 4 11 19 11
0 3 4 11
1 1 3 16 1 11
1 3 5 11 18 31
1 1 5 1 1 13
0 4 5 10
1 3 2 5 4 30
1 1 1 1 16 41
1 1 5 3 14 39
0 4 2 31
1 3 3 13 9 29
0 2 3 14
1 5 1 2 16 13输出样例2
0 17 3 14 14数据规模
对于 $50\%$ 的数据，$n,m \le 1000$。
另有 $20\%$ 的数据，保证只有普通道路。
对于 $100%$ 的数据，$1 \le n,m \le 5\times 10^5$ , $0 \le t_0, t, w \le 10^9$， $t>0$ 。
时间限制：1000 ms
内存限制：512 MB
怎么考虑呢？首先发现无论是普通道路还是地铁道路，所耗的代价不会变小，所以果断dijkstra。
普通道路其实很好去迭代。那么地铁道路我们需要通过与 \(t\) 的模数求出下一次地铁到达的时间，然后再加上 \(w\) 就行了。
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
typedef long long LL;
int n,m,hd[N],e_num,w,op,t0,t,vis[N],u,v;
LL dis[N];
struct edge{
int v,nxt,op,t0,t,w;
}e[N<<1];
struct node{
int v;
LL w;
bool operator<(const node&n)const{
return w>n.w;
}
};
priority_queue<node>q;
void add_edge(int op,int t0,int t,int u,int v,int w)
{
e[++e_num]=(edge){v,hd[u],op,t0,t,w};
hd[u]=e_num;
}
LL dist(LL u,int ed)
{
if(!e[ed].op)
return u+e[ed].w;
if(u<e[ed].t0)
return e[ed].t0+e[ed].w;
if((u-e[ed].t0)%e[ed].t==0)
return u+e[ed].w;
return (u-e[ed].t0+e[ed].t-1)/e[ed].t*e[ed].t+e[ed].t0+e[ed].w;
}
void dijkstra()
{
memset(dis,0x7f,sizeof(dis));
dis[1]=0;
q.push((node){1,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(dist(dis[k],i)<dis[e[i].v])
{
dis[e[i].v]=dist(dis[k],i);
q.push((node){e[i].v,dis[e[i].v]});
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d",&op);
if(!op)
{
scanf("%d%d%d",&u,&v,&w);
add_edge(0,0,0,u,v,w);
add_edge(0,0,0,v,u,w);
}
else
{
scanf("%d%d%d%d%d",&u,&v,&t0,&t,&w);
add_edge(1,t0,t,u,v,w);
}
}
dijkstra();
for(int i=1;i<=n;i++)
printf("%lld ",dis[i]);
return 0;
}