Module: الگوریتم فلوید


Problem

1/10

Floyd: The Beginning (C++)

Theory Click to read/hide

Error

Problem

یک نمودار جهت دار داده می شود که به لبه های آن وزن های غیر منفی (طول) اختصاص داده شده است. طول کوتاه ترین مسیر را از راس s تا راس t را پیدا کنید.
 
ورودی
خط اول شامل سه عدد است: تعداد رئوس در نمودار N ≤50، اعداد رئوس s و t. بعد ماتریس مجاورت نمودار می آید، یعنی N ردیف که هر کدام حاوی N عدد است. عدد j در ردیف i ام ماتریس مجاورت طول یال منتهی به راس i به j ام را مشخص می کند. طول ها می توانند هر مقداری از 0 تا 1000000 داشته باشند، عدد -1 به این معنی است که لبه مربوطه وجود ندارد. وجود صفر در مورب اصلی ماتریس تضمین شده است.
 
خروجی
چاپ یک عدد – حداقل طول مسیر اگر مسیر وجود ندارد، -1 را چاپ کنید.

نمونه‌ها <سر> <بدن>
# ورودی خروجی
1
3 1 2
0 -1 3
7 0 1
2 215 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!