1915G - Bicycles - CodeForces Solution

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define mod 1000000007
#define int long long


int32_t main (){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
    int tt;
  cin >> tt;
  while (tt--) {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> g(n);
    for (int i = 0; i < m; i++) {
      int a, b, c;
      cin >> a >> b >> c;
      --a; --b;
      g[a].emplace_back(b, c);
      g[b].emplace_back(a, c);
    }
    vector<int> w(n);
    for (int i = 0; i < n; i++) {
      cin >> w[i];
    }
    vector<vector<int>> dist(n, vector<int>(n, numeric_limits<int>::max()));
    priority_queue<array<int, 3>, vector<array<int, 3>>, greater<array<int, 3>>> s;
    dist[0][0] = 0;
    s.push({dist[0][0], 0, 0});
    while (!s.empty()) {
      int expected = s.top()[0];
      int i = s.top()[1];
      int j = s.top()[2];
      s.pop();
      if (dist[i][j] != expected) {
        continue;
      }
      if (i == n - 1) {
        cout << dist[i][j] << '\n';
        break;
      }
      for (auto& p : g[i]) {
        int ti = p.first;
        int tj = (w[j] < w[p.first] ? j : p.first);
        if (dist[i][j] + p.second * w[j] < dist[ti][tj]) {
          dist[ti][tj] = dist[i][j] + p.second * w[j];
          s.push({dist[ti][tj], ti, tj});
        }
      }
    }
  }
  return 0;
}