Pagini recente » Monitorul de evaluare | Cod sursa (job #1034387) | onisim2009-7 | Cod sursa (job #1004018) | Cod sursa (job #3224748)
#include <fstream>
#include <climits>
#include <vector>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
const int nmax = 50005;
const int inf = INT_MAX;
int fr[nmax], n, m, cost[nmax];
vector< pair<int, int> > a[nmax];
void Dij(int nod)
{
fr[nod] = 1;
while(a[nod].size())
{
pair<int, int> k = a[nod].back();
a[nod].pop_back();
cost[k.first] = min(cost[k.first], k.second + cost[nod]);
if(!fr[k.first])
Dij(k.first);
}
}
int main()
{
f >> n >> m;
for(int i = 1; i <= n; i ++)
{
int x, y, c;
f >> x >> y >> c;
a[x].push_back({y, c});
}
for(int i = 2; i <= n; i ++)
cost[i] = inf;
Dij(1);
for(int i = 2; i <= n; i ++)
if(cost[i] == inf)
g << 0 << " ";
else
g << cost[i] << " ";
return 0;
}