Problem

1/10

فلويد: البداية (C ++)

Theory Click to read/hide

Error

Problem

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

أمثلة <الجسم>
# إدخال الإخراج
1
3 1 2
0-1 3
7 0 1
2215 0
218

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 <vector>
#include <iostream>
#include <climits>
using namespace std;

const int inf = INT_MAX;

int main()
{
	int n, s, t;
	cin >> n >> s >> t;
	vector<vector<int> > d(n + 1, vector<int>(n + 1,inf));
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			int a;
			cin >> a;
			if (a != -1)
			{
				d[i + 1][j + 1] = a;
			}
		}
	}
	for (int k = 1; k <= n; ++k)
	{
		for (int i = 1; i <= n; ++i)
		{
			for (int j = 1; j <= n; ++j)
			{      
			}
		}
	}
	if (d[s][t] == inf)
	{
		cout << -1;
		return 0;
	}
	cout << d[s][t] << endl;

}

     

Program check result

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