Problem

1/14

Dijkstra: البداية (C ++)

Theory Click to read/hide

إعطاء رسم بياني مرجح موجه أو غير موجه برؤوس n وحواف m. أوزان جميع الحواف غير سالبة. تم تحديد بعض قمة البداية s. تحتاج إلى العثور على أطوال أقصر المسارات من قمة الرأس s إلى جميع الرؤوس الأخرى ، وكذلك توفير طريقة لطباعة أقصر المسارات نفسها.
& nbsp؛
تسمى هذه المشكلة "مشكلة أقصر مسار بمصدر واحد" (مصدر واحد مشكلة أقصر المسارات).
يؤدي نفس المهام مثل 1-K BFS ، ولكن بغض النظر عن K. أيضًا ، مثل 1-K BFS ، فإنه لا يتعامل بشكل صحيح مع الحواف السلبية

الخوارزمية :
تتكون خوارزمية Dijkstra نفسها من تكرارات N. في التكرار التالي ، قمة الرأس V & nbsp؛ مع أصغر مسافة إليه من بين القمم التي لم يتم تحديدها بعد ، يتم تمييز هذا الرأس ويحدث ارتخاء القمم المجاورة منه.


& nbsp ؛ السلوك المقارب النهائي للخوارزمية هو: O (n 2 + m)

Problem

يتم إعطاؤك رسم بياني مرجح موجه. أوجد أقصر مسافة من رأس معين إلى آخر.
& nbsp؛
إدخال
يحتوي السطر الأول على ثلاثة أرقام: N و S و F (1 & le؛ N & le؛ 100، 1 & le؛ S، F & le؛ N) ، حيث N & ndash؛ عدد رؤوس الرسم البياني ، S & ndash ؛ الرأس الأولي و F & ndash؛ أخير. في السطور N التالية ، أدخل أرقام N لكل منها ، بما لا يتجاوز 100 ، & ndash؛ مصفوفة الوزن المجاورة للرسم البياني ، حيث تعني -1 عدم وجود حافة بين الرؤوس وأي رقم غير سالب & ndash؛ وجود حافة وزن معين. الأصفار مكتوبة على القطر الرئيسي للمصفوفة.
& nbsp؛
الإخراج
مطلوب عرض المسافة المرغوبة أو -1 إذا لم يكن هناك مسار بين الرؤوس المحددة.

أمثلة <الجسم>
# إدخال الإخراج
1
3 2 1
0 1 1
4 0 1
2 1 0
3

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++
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!