#include<iostream>
#include<vector>
using namespace std;

void Dijkstra (vector<vector<pair<int,int>>>&,int&);

int main(){
setlocale(LC_ALL,"Russian");
vector<vector<pair<int,int>>>G{ //запись данногографа
{{1,1},{3,6}},
{{0,1},{2,4},{3,3},{4,9},{5,8},{6,7}},
{{0,6},{1,4}},
{{1,3},{4,2}},
{{3,2},{1,9}},
{{1,8},{6,5}},
{{1,7},{5,5}}
};
int vortex; // ввод переменной vortex
cout<<"Введите номер вершины:"; // запись в vortex вершину от которой ведем поиск наименьшего пути
cin>>vortex;
Dijkstra(G,vortex);// вызов функции

return 0;
}

void Dijkstra(vector<vector<pair<int,int>>>&myG,int&s){// описание функции ввод графа и вершины отсчета
const int inf =2000000000; //задаем значение infinity
size_t n =myG.size(); // присваиваем н длину G
vector<size_t>D(n,inf); // создание вектора D длинной n и со значениями inf, для хранения кратчайших путей в графе от вершины
vector<size_t>P(n); // создание вектора P с длиной n, для хранения промежуточных значений длин путей
vector<bool>U(n,false); // создание вектора длиной n со значениями false для того, чтобы отметить пройденные вершины
D[s]=0;// присваиваем исходной вершине значение 0
for(size_t i=0;i<n;i++){
size_t v=1000000000;// Определяем максимальное значение стартовой вершины
for(size_t j=0;j<n;j++)
if(!U[j]&&(v==1000000000||D[j]<D[v]))// если вершина не помечена, имеет максимальное значение или D[j]<D[v], то
v=j;// значению вершины присваивается j
if(D[v]==inf)// если значение вершины не изменилось, то переходим к следующей
break;
U[v]=true;// помечаем вершину как пройденную
auto beg=myG[v].begin();//присваиваем beg первый элемент myG[v]
auto lst=myG[v].end();// присваиваем lst последний элемент myG[v]
while(beg!=lst){// поиск наименьшего пути
auto to=beg->first;
auto len=beg->second;
if(D[v]+len<D[to]){// выбор лучшего значения + длины до некоторой вершины и прямого пути до некоторой вершины
D[to]=D[v]+len;
P[to]=v;
}
beg++;// рассматриваем следующую вершину
}
}
for(auto&r:D)//вывод вектора
cout<<r<<"";
cout<<endl;
}