Problem

1/14

Dijkstra: Sự khởi đầu (C++)

Theory Click to read/hide

Cho một đồ thị có trọng số có hướng hoặc vô hướng có n đỉnh và m cạnh. Trọng số của tất cả các cạnh là không âm. Một số đỉnh bắt đầu s được chỉ định. Bạn cần tìm độ dài của các đường đi ngắn nhất từ ​​đỉnh s đến tất cả các đỉnh khác, đồng thời cung cấp cách tự in các đường đi ngắn nhất.
 
Vấn đề này được gọi là "vấn đề đường dẫn ngắn nhất nguồn đơn" (vấn đề đường đi ngắn nhất từ ​​một nguồn).

Thực hiện các tác vụ giống như 1-K BFS, nhưng không liên quan đến K. Ngoài ra, giống như 1-K BFS, nó không xử lý đúng các cạnh âm

Thuật toán:
Bản thân thuật toán Dijkstra bao gồm N lần lặp. Ở lần lặp tiếp theo, đỉnh V  với khoảng cách nhỏ nhất đến nó trong số các đỉnh chưa được đánh dấu, đỉnh này sẽ được đánh dấu và các đỉnh lân cận xảy ra từ nó.


 hành vi tiệm cận cuối cùng của thuật toán là: O(n2+ m)

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, S và F (1≤ N≤ 100, 1≤ S, F≤ N), trong đó N – số đỉnh của đồ thị, 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ề trọng số của đồ thị, trong đó -1 có nghĩa là không có cạnh giữa các đỉnh và mọi số không âm – 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>

time 1000 ms
memory 32 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
# Đầu vào Đầu ra
1
3 2 1
0 1 1
4 0 1
2 1 0
 3
Write the program below 
#include<iostream>
 
using namespace std;
 
int main()
{
    const int N1 = 110;
    int N, S, F, g[N1][N1], i, j, mini, d[N1];
    bool used[N1];
   
    cin >> N >> S >> F;
   
    fill(used, used + N, false);
   
    fill(d, d + N, 10000000);
   
    for (i = 0; i < N; i++)
    {
        for (j = 0; j < N; j++)
            cin >> g[i][j];
    }
   
    d[S - 1] = 0;
   
    for (i = 0; i < N; i++)
    {
        mini = -1;
       
        for (j = 0; j < N; j++)
        {
            if (!used[j] && (mini == -1 || d[j] < d[mini]))
                mini = j;
        }
       
        used[mini] = true; 
    if (d[F - 1] == 10000000)
        cout << "-1";
    else
        cout << d[F - 1];
}

     

Program check result

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