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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=1e5+5;
const double Pi=acos(-1);
const ll Mod=1e9+7;
vector<pair<ll,int> >mp[Max],Magic;
bool vis[Max],visS[Max],visT[Max];
ll dis[Max];
int n,m;
void Dijkstra(int S){
for(int i=1;i<=n;i++)dis[i]=1e18;
dis[S]=0;
priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > >q;
q.push({0,S});
while(!q.empty()){
int now=q.top().second;q.pop();
if(vis[now])continue;
vis[now]=1;
for(auto i:mp[now]){
int to=i.second;ll cost=i.first;
if(dis[to]>dis[now]+cost){
dis[to]=dis[now]+cost;
q.push({dis[to],to});
}
}
}
}
int main(){
Turnoff;
cin>>n>>m;
for(int i=0;i<n;i++){
ll temp;cin>>temp;
Magic.push_back({temp,i+1});
}
sort(Magic.begin(),Magic.end());
for(int i=1;i<=m;i++){
ll u,v,w;cin>>u>>v>>w;
mp[u].push_back({w,v});
mp[v].push_back({w,u});
}
int S,T;cin>>S>>T;
for(int i=1;i<Magic.size();i++){
int u=Magic[i-1].second,v=Magic[i].second;
ll w=Magic[i].first-Magic[i-1].first;
mp[u].push_back({w,v});
mp[v].push_back({w,u});
}
Dijkstra(S);
cout<<dis[T]<<endl;
}
|