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

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

Дан ориентированный взвешенный граф. Найдите кратчайший путь от одной заданной вершины до другой.

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

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

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


    #include<iostream>

#include<stack>

#include<set>

#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],p[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;p[s]=s;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];p[j]=i;

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

    if(d[f]<INF){stack<int>q;q.push(f);	

	while(f!=s){f=p[f];q.push(f);}

	while(!q.empty()){

		cout<<q.top()+1<<' ';q.pop();}}

    else cout<<-1;

return 0;}

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