Алгоритм Дейкстры

const int INF = 1000000000;
int main() {
int n;
... чтение n ...
vector < vector < pair<int,int> > > g (n);
... чтение графа ...
int s = ...; // стартовая вершина
vector<int> d (n, INF), p (n);
d[s] = 0;
vector<char> u (n);
for (int i=0; i<n; ++i) {
int v = -1;
for (int j=0; j<n; ++j)
if (!u[j] && (v == -1 || d[j] < d[v]))
v = j;
if (d[v] == INF)
u[v] = true;
for (size_t j=0; j<g[v].size(); ++j) {
int to = g[v][j].first,
len = g[v][j].second;
if (d[v] + len < d[to]) {
d[to] = d[v] + len;
p[to] = v;
}
}
}
}

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
 
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
 
typedef boost::adjacency_list <boost::listS, boost::vecS, boost::directedS,
   boost::no_property, boost::property <boost::edge_weight_t, int>> graph_type;
typedef boost::graph_traits <graph_type>::vertex_descriptor vertex_descriptor;
typedef boost::graph_traits <graph_type>::edge_descriptor edge_descriptor;
typedef std::pair <int, int> edge;
 
const int Number_Nodes = 6;
enum nodes { A, B, C, D, E, F };
 
int main() {
   std::string nodes_name = "ABCDEF";
   std::vector <edge> edges_array = { 
                        edge(A, B), edge(A, C), edge(A, F),
                        edge(B, C), edge(B, D), edge(C, D),
                        edge(C, F), edge(D, E), edge(E, F)
                      };
   std::vector <int> weights_array = { 7, 9, 14, 10, 15, 11, 2, 6, 9 };
   
   graph_type graph(
      edges_array.begin(),
      edges_array.end(),
      weights_array.begin(),
      Number_Nodes
   );
   
   std::vector <vertex_descriptor> p(boost::num_vertices(graph));
   std::vector <int> distance_array(boost::num_vertices(graph));
   vertex_descriptor s = boost::vertex(A, graph);
   
   boost::dijkstra_shortest_paths(
      graph,
      s, 
      boost::predecessor_map(&(*p.begin())).distance_map(&(*distance_array.begin()))
   );
   
   boost::graph_traits <graph_type>::vertex_iterator vp, vend;
   boost::tie(vp, vend) = vertices(graph);
 
   std::for_each(
      vp,
      vend,
      [&nodes_name, &distance_array](int value) {
         std::cout << "distance to " << nodes_name[value] 
                   << " equal to "   << distance_array[value] << "\n";
      }
   );
}

#include <iostream>
#include <cstdio>
 
using namespace std;
 
int g[150][150];
 
bool used[150];
 
int d[150];
 
const int inf = 1000000000;
 
int main()
{
    freopen("input.txt","r",stdin); // если файлы не нужны то эти 2 строки удалить
    freopen("output.txt","w",stdout);
    int n, s;
    cin >> n >> s;
    s--; //нумерация массивов в с++ идет с нуля
    for (int i = 0; i < n; i++)
         for (int j = 0; j < n; j++)
             cin >> g[i][j]; //считывание графа
    for (int i = 0; i < n; i++)
        d[i] = inf;
    d[s] = 0;
    for (int i = 0; i < n; i++)
        {
            int v = -1;
            for (int j = 0; j < n; j++)
                 if (!used[j])
                      if (v == -1 || d[j] < d[v])
                           v = j; //нахождение вершины с минимальной меткой
             used[v] = true;
             for (int j = 0; j < n; j++)
                  if (g[v][j] != -1 && i!=j)
                      d[j] = min(d[v] + g[v][j], d[j]);//релаклации через эту вершину
         }
    for (int i = 0; i < n; i++)
         if (d[i] == inf)
             cout << -1 << ' ';
          else
             cout << d[i] << ' ';//вывод ответа
return 0;
}