Problem

1/10

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

Theory Click to read/hide

Error

Problem

Cho một đồ thị có hướng có các cạnh được gán một số trọng số (độ dài) không âm. Tìm độ dài của đường đi ngắn nhất từ ​​đỉnh s đến đỉnh t.
 
Đầu vào
Dòng đầu tiên chứa ba số: số đỉnh của đồ thị N ≤50, số đỉnh s và t. Tiếp theo là ma trận kề của đồ thị, tức là N hàng, mỗi hàng chứa N số. Số thứ j trong hàng thứ i của ma trận kề xác định độ dài của cạnh dẫn từ đỉnh thứ i đến đỉnh thứ j. Độ dài có thể lấy bất kỳ giá trị nào từ 0 đến 1000000, số -1 có nghĩa là không có cạnh tương ứng. Đảm bảo rằng không có số 0 trên đường chéo chính của ma trận.
 
Đầu ra
In một số duy nhất – chiều dài đường đi tối thiểu. Nếu đường dẫn không tồn tại, hãy in -1.

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 1 2
0 -1 3
7 0 1
2 215 0
 218
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!