Problem

9/14

Thuật toán Dijkstra trong O(M logN) với priority_queue: Start (C++)

Problem

Bạn được cung cấp một biểu đồ trọng số có hướng. Tìm khoảng cách ngắn nhất từ ​​đỉnh này đến đỉnh khác.
 
Đầu vào
Dòng đầu tiên chứa ba số: N, M, S và F (1≤ N≤ 100, 1≤ S, F≤ N), trong đó N – số đỉnh của đồ thị, M – số lượng xương sườn,  S– đỉnh ban đầu và F – cuối cùng. Trong N dòng tiếp theo, hãy nhập N số mỗi dòng, không quá 100, – ma trận kề của đồ thị, trong đó -1 có nghĩa là không có cạnh giữa các đỉnh và bất kỳ số không âm nào – sự hiện diện của một cạnh của trọng lượng nhất định. Các số 0 được viết trên đường chéo chính của ma trận.
 
Đầu ra
Cần hiển thị khoảng cách mong muốn hoặc -1 nếu không có đường đi giữa các đỉnh đã chỉ định.

Ví dụ <đầu>
# Đầu vào Đầu ra
1 4 4 3 4
3 1 3
1 2 3
2 4 3
3 4 10
9
Write the program below
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

    const int INF = 1000000000;

    int main() {
        int n, m ,s, f;
        cin >> n>>m>>s>>f;
        
        vector < vector < pair<int, int> > > g(n+1);
         for (int i = 0; i < m; i++)
        {
            int x, y, z;
            cin >> x >> y >> z;
            g[x].push_back(make_pair(y, z));
        }

        vector<int> d(n+1, INF);
        d[s] = 0;
        priority_queue < pair<int, int> > q;
        q.push(make_pair(0, s));
        while (!q.empty()) {
            int v = q.top().second, cur_d = -q.top().first;
            q.pop();
            if (cur_d > d[v])  continue;

            for (size_t j = 0; j < g[v].size(); ++j) {
                int to = g[v][j].first,
                    len = g[v][j].second;
                if (d[v] + len < d[to]) {
                    d[to] = d[v] + len;
                    
                    q.push(make_pair(-d[to], to));
                }
            }
        }    
}    

     

Program check result

To check the solution of the problem, you need to register or log in!