Module: 플로이드 알고리즘


Problem

1/10

플로이드: 더 비기닝(C++)

Theory Click to read/hide

Error

Problem

가장자리에 음수가 아닌 가중치(길이)가 할당된 유향 그래프가 있습니다. 정점 s에서 정점 t까지의 최단 경로 길이를 찾으십시오.
 
입력
첫 번째 줄에는 세 개의 숫자가 포함되어 있습니다: 그래프의 정점 수 N≤50, 정점 수 s 및 t. 다음은 그래프의 인접 행렬, 즉 각각 N개의 숫자를 포함하는 N개의 행입니다. 인접 행렬의 i번째 행의 j번째 숫자는 i번째 꼭지점에서 j번째 꼭지점까지 이어지는 가장자리의 길이를 지정합니다. 길이는 0에서 1000000 사이의 값을 가질 수 있으며 숫자 -1은 해당 가장자리가 없음을 의미합니다. 행렬의 주 대각선에 0이 있음을 보장합니다.
 
출력
단일 숫자 인쇄 – 최소 경로 길이. 경로가 존재하지 않으면 -1을 인쇄합니다.

예 <헤드> <일># <몸>

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++
입력 출력
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!