-
-
Save enzerr/4b4c767bfd3cb2c4913e55db37668145 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include<bits/stdc++.h> | |
using namespace std; | |
#define all(x) x.begin(),x.end() | |
#define tii tuple<int,int,int> | |
#define pb push_back | |
#define fr first | |
#define sc second | |
#define mp make_pair | |
#define int long long | |
const int maxn = 1e5+10; | |
int n, m, k, p[maxn]; | |
map<int,vector<int>> g[maxn]; | |
map<int,int> d[maxn]; | |
void solve() { | |
cin >> n >> m >> k; | |
for(int i = 1; i <= k; i++) { | |
cin >> p[i]; | |
} | |
for(int i = 0; i < m; i++) { | |
int u,v,w; cin >> u >> v >> w; | |
g[u][w].pb(v); | |
g[v][w].pb(u); | |
} | |
int s,t; cin >> s >> t; | |
priority_queue<tii,vector<tii>,greater<tii> pq; | |
d[s][0] = 0; | |
pq.push({0,s,0}); | |
while(pq.size()) { | |
auto[dist,u,w] = pq.top(); pq.pop(); | |
if(d[u][w] != dis) continue; | |
if(w == 0) { | |
for(auto X : g[u]) { | |
int id = X.fr; | |
if(d[u].count(id) == 0 or d[u][w]+p[id] < d[u][id]) { | |
d[u][id] = d[u][w]+p[id]; | |
pq.push({d[u][id],u,id}); | |
} | |
} | |
} | |
else { | |
if(d[u].count(0) == 0 or d[u][w] < d[u][0]) { | |
d[u][0] = d[u][w]; | |
pq.push({d[u][0],u,0}); | |
} | |
for(auto v : g[u][w]) { | |
if(d[v].count(w) == 0 or d[u][w] < d[v][w]) { | |
d[v][w] = d[u][w]; | |
pq.push({d[v][w],v,w}); | |
} | |
} | |
} | |
} | |
if(d[t].count(0) == 0) { | |
cout << -1 << endl; | |
} | |
else { | |
cout << d[t][0] << endl; | |
} | |
} | |
int32_t main() { | |
solve(); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment