Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define int li
- struct Edge {
- int to, cost;
- };
- void solve(__attribute__((unused)) bool read) {
- int n, m;
- cin >> n >> m;
- vector<vector<Edge>> g(n);
- for (int i = 0; i < m; ++i) {
- int a, b, cost;
- cin >> a >> b >> cost;
- --a; --b;
- g[a].push_back({b, cost});
- g[b].push_back({a, cost});
- }
- priority_queue<pair<int, int>> q;
- const int INF = (int)1e18;
- vector<int> dist(n, INF);
- dist[0] = 0;
- q.push({0, 0});
- vector<char> used(n, false);
- while (!q.empty()) {
- int v = q.top().second;
- q.pop();
- if (used[v]) {
- continue;
- }
- used[v] = true;
- for (auto e : g[v]) {
- int candy = e.cost + dist[v];
- if (candy < dist[e.to]) {
- dist[e.to] = candy;
- q.push({dist[e.to], e.to});
- }
- }
- }
- int res = dist[n - 1];
- if (res == INF) {
- res = -1;
- }
- cout << res << "\n";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement