if (used[j] == 0 && g[v][j] != -1) {
relax(v, j, g[v][j]);
p[j] = v;
}
for (int v = f; v != s; v = p[v]) {
path.push_back(v);
}
path.push_back (s);
reverse(path.begin(), path.end());
for (auto elem: path)
{
cout << elem << ' ';
}
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
//int g[20000][2000], used[20000], dist[20000];
vector<int> dist(6, INT_MAX);
vector<bool> used(6);
void relax(int i, int j, int h){
if (dist[i] + h < dist[j])
dist[j] = dist[i] + h;
}
int main() {
int n, s, f, v, min;
cin >> n >> s >> f;
--s;
--f;
int g[n][n];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cin >> g[i][j];
}
}
used.resize(n);
dist.resize(n);
dist[s] = 0;
for(int i = 1; i < n; i++)
{
min = INT_MAX;
v = -1;
for(int j = 0; j < n; j++)
if (used[j] == 0 && dist[j] < min) {min = dist[j]; v = j;}
if (v < 0) break;
for( int j = 0; j < n; j++)
if (used[j] == 0 && g[v][j] != -1)
relax(v,j,g[v][j]);
used[v] = 1;
}
if (dist[f] == INT_MAX) {
cout << "-1";
return 0;
}
cout << dist[f];
}
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
//int g[20000][2000], used[20000], dist[20000];
vector<int> dist(6, INT_MAX);
vector<bool> used(6);
void relax(int i, int j, int h){
if (dist[i] + h < dist[j])
dist[j] = dist[i] + h;
}
int main() {
int n, s, f, v, min;
cin >> n >> s >> f;
//--s;
//--f;
int g[n][n];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cin >> g[i][j];
}
}
used.resize(n);
dist.resize(n);
dist[s] = 0;
for(int i = 1; i < n; i++)
{
min = INT_MAX;
v = -1;
for(int j = 0; j < n; j++)
if (used[j] == 0 && dist[j] < min) {min = dist[j]; v = j;}
if (v < 0) break;
for( int j = 0; j < n; j++)
if (used[j] == 0 && g[v][j] != -1)
relax(v,j,g[v][j]);
used[v] = 1;
}
if (dist[f] == INT_MAX) {
cout << "-1";
return 0;
}
cout << dist[f];
}