Pagini recente » Borderou de evaluare (job #46853) | Cod sursa (job #2011445) | Rezultatele filtrării | Cod sursa (job #843373) | Cod sursa (job #769845)
Cod sursa(job #769845)
#include <fstream>
#include <vector>
#include <queue>
#define NLen 0x10000
#define inf 0x7fffffff
using namespace std;
ifstream fi;
ofstream fo;
vector < pair < int, int > > g[NLen];
int dist[NLen];
int N;
class ComparePQ
{
public:
bool operator()(const int & a, const int & b)
{
return dist[a] > dist[b];
}
};
inline void dij(int nod)
{
priority_queue < int, vector < int > , ComparePQ > PQ;
for(int i = 1; i <= N; ++ i) dist[i] = inf;
dist[nod] = 0;
PQ.push(nod);
while( ! PQ.empty())
{
nod = PQ.top();
PQ.pop();
for(int i = 0; i < g[nod].size(); ++ i)
if(dist[ g[nod][i].first ] == inf || dist[ g[nod][i].first ] > dist[nod] + g[nod][i].second)
{
dist[ g[nod][i].first ] = dist[nod] + g[nod][i].second;
PQ.push(g[nod][i].first);
}
}
}
int main()
{
int M, x, y, c;
fi.open("dijkstra.in");
fi >> N >> M;
for(; M -- ; )
{
fi >> x >> y >> c;
g[x].push_back(make_pair(y, c));
}
fi.close();
dij(1);
fo.open("dijkstra.out");
for(int i = 2; i <= N; ++ i) fo << dist[i] << ' ';
fo << '\n';
fo.close();
return 0;
}