Pagini recente » Profil PaulDB | Atasamentele paginii Profil o0ana7 | Borderou de evaluare (job #1476332) | Atasamentele paginii Factorial | Cod sursa (job #3204601)
#include <bits/stdc++.h>
using namespace std;
const int oo = 1e9;
int n, m;
int d[50009], use[50009];
vector<pair<int, int>> g[50009];
void dijkstra(int source)
{
for (int i = 2; i <= n; i++) d[i]=oo;
for (int i = 1; i <= n; i++)
{
int min=oo, nod;
for (int i = 1; i <= n; i++)
if (d[i] < min && use[i] == 0)
{
min = d[i], nod=i;
use[nod]=1;
for (int i = 0; i < (int)g[nod].size(); ++i)
{
int vecin = g[nod][i].first;
int cost = g[nod][i].second;
if (d[nod] + cost < d[vecin])
d[vecin] = d[nod] + cost;
}
}
}
}
ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");
int main()
{
fin >> n >> m;
for (int i = 0; i < m; i++)
{
int x, y, c;
fin >> x >> y >> c;
g[x].push_back(make_pair(y, c));
}
dijkstra(1);
for (int i = 2; i <= n; i++)
fout << d[i] << " ";
return 0;
}