Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- using namespace std;
- const int N = 2e5 + 5;
- const int inf = 2e9;
- int n, m, s, t;
- long long dist[N];
- vector < pair <int, int> > g[N];
- int main(){
- for (int i = 0; i < N; i++) {
- dist[i] = inf;
- }
- cin >> n >> m >> s >> t;
- for (int i = 1; i <= m; i++) {
- int u, v, len;
- cin >> u >> v >> len;
- g[u].push_back(make_pair(v, len));
- g[v].push_back(make_pair(u, len));
- }
- set < pair <int, int> > st;
- dist[s] = 0;
- st.insert({dist[s], s});
- while (!st.empty()) {
- int v = st.begin()->second;
- st.erase(st.begin());
- for (int i = 0; i < g[v].size(); i++) {
- int to = g[v][i].first, len = g[v][i].second;
- if (dist[v] + len < dist[to]) {
- st.erase({dist[to], to});
- dist[to] = dist[v] + len;
- st.insert({dist[to], to});
- }
- }
- }
- if (dist[t] == inf) {
- cout << -1 << endl;
- } else {
- cout << dist[t] << endl;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement