Решение задачи №132 «Алгоритм Дейкстры» с ACMP

Условие задачи

Дан ориентированный взвешенный граф. Для него вам необходимо найти кратчайшее расстояние от вершины S до вершины F.

Входные данные
В первой строке входного файла INPUT.TXT записаны три числа: N, S и F (1 ≤ N ≤ 100; 1 ≤ S, F ≤ N), где N - количество вершин графа. В следующих N строках записаны по N чисел - матрица смежности графа, где число в i-ой строке j-ом столбце соответствует ребру из i в j: -1 означает отсутствие ребра между вершинами, а любое неотрицательное целое число (от 0 до 100) - наличие ребра данного веса. На главной диагонали матрицы всегда записаны нули.

Выходные данные
В выходной файл OUTPUT.TXT необходимо вывести искомое расстояние или -1, если пути между указанными вершинами не существует.

Решение на C++


    #include<set>

#include<iostream>

#define INF 1000000000

using namespace std;

int main(){

	int n,m,i,f,j,k,s,t;set<pair<int,int>>c;

	cin>>n>>s>>f;s--;f--;

	int a[n][n],d[n];bool b[n];

	for(i=0;i<n;++i){

	d[i]=INF;b[i]=true;

	for(j=0;j<n;++j){

		cin>>a[i][j];

		if(a[i][j]<0)a[i][j]=INF;}}

	d[s]=0;c.insert(make_pair(0,s));

	while(!c.empty()){

		i=c.begin()->second;b[i]=false;

		c.erase(c.begin());

		for(j=0;j<n;++j)

			if(b[j]&&d[j]>d[i]+a[i][j]){

				c.erase(make_pair(d[j],j));

				d[j]=d[i]+a[i][j];

				c.insert(make_pair(d[j],j));}}

	if(d[f]<INF)cout<<d[f];

	else cout<<-1;

return 0;}

Условия задач взяты с сайта acmp.ru