题目:https://atcoder.jp/contests/abc463/tasks/abc463_e?lang=en
一
题目求\(1\)至点\(2\)到\(n\)的距离，出发点相同，终点不同，是单源最短路径问题，考虑bfs。
二
在题目描述中：
此外，每个城市都安装了曲速门，使用曲速门可以在 \(X _ i+X _ j+Y\) 分钟内从城市 \(i\ (1\le i\le N)\) 到达城市 \(j\ (1\le j\le N)\) 。
可以考虑到从中对于一个点\(j\)，改变是否曲速门到达此\(j\)的因素只有\(X _ i+\)\(1\)到\(i\)的时间,因此，考虑一个变量\(mi\)，存\(X _ i+\)\(1\)到\(i\)的时间的最小值。
由于\(mi\)的值包含 \(1\)到\(i\)的时间，则我们不必关注\(i\)的值，只需计算\(X _ j=mi+X _ j+Y\)
代码解析
第一部分，变量
#include<bits/stdc++.h>//万能头
using namespace std;
#define int long long//把所有int替换为long long
const int N=200010;//n 的最大值
int n,m,x[N],y;//题目里的n,m,x[i],y
vector<pair<int,int>>e[N];//vector 存边
//（i指从哪来，e[i].first指去哪，e[i].second指路程)
int d[N];//1到i的距离
第二部分，输入
signed main(){//define后,int会改为long long 主函数返回值应为int(signed=int)cin>>n>>m>>y;for(int i=1;i<=m;i++){int u,v,t;cin>>u>>v>>t;//vector 存双向边e[u].push_back({v,t});e[v].push_back({u,t});}for(int i=1;i<=n;i++)cin>>x[i];//题中的x[i]
第三部分，初始化
for(int i=1;i<=n;i++)d[i]=LLONG_MAX;//1至i的距离默认为INF(无法到达)for(int i=2;i<=n;i++) e[i].push_back({i-1,LLONG_MAX/2}),e[i-1].push_back({i,LLONG_MAX/2});//曲速门不在e里，用i至i-1长度为INF/2(留一点空间)保证图联通d[1]=0;//1至1的距离为0priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;//小根堆first指路程，second指去哪 (pair<int,int>比大小优先看.first)q.push({0,1});//在int mi=LLONG_MAX;//初始化mi
第四部分，bfs
while(!q.empty()){int w=q.top().first,u=q.top().second;q.pop();if(w!=d[u])continue;//是否最新if(mi!=LLONG_MAX){//mi里是否存过数int v=mi+x[u]+y;//计算长度if(d[u]>v){d[u]=v;//更新q.push({d[u],u});//从自己到自己，从新进入循环continue;//离开本次循环}}mi=min(mi,d[u]+x[u]);//更新mifor(auto i:e[u]){//正常bfsint v=i.first,t=i.second;if(d[v]>d[u]+t){d[v]=d[u]+t;q.push({d[v],v});}}}for(int i=2;i<=n;i++)cout<<d[i]<<" ";//输出return 0;
}