Pagini recente » Cod sursa (job #676993) | Cod sursa (job #2978612) | Cod sursa (job #2609044) | Cod sursa (job #112135) | Cod sursa (job #1971963)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#define alot 2e9
using namespace std;
int n, m;
class nod{
public:
unsigned int id;
vector <pair <int, int> > vecini ; //se va inlocui cu lista
};
class cmp{
public:
bool operator () (pair <int, int> p1, pair <int, int> p2)
{
return p1.second > p2.second;
}
};
priority_queue <pair <int, int>,
vector<pair <int, int> >,
cmp> Q; ///fa dracia de heap fara liste de vecini!!!
vector <nod> G (50001);
vector <int> dist (50001);
//vector <bool> vizitat (50001);
bitset <50001> vizitat;
int main()
{
int i, x, y, z;
ifstream g ("dijkstra.in");
ofstream h ("dijkstra.out");
int curr;
g>>n>>m;
//G.resize(n+1);
//vizitat.resize(n+1);
//dist.resize(n+1);
for(i=0;i<m;i++)
{
g>>x>>y>>z;
G[x].vecini.push_back(make_pair(y, z));
G[x].id = x;
}
dist[1]=0;
for(i=2;i<=n;++i)
dist[i]=alot;
Q.push(make_pair(G[1].id, dist[1]));
while (!Q.empty())
{
/*for (i=1;i<=n;++i)
cout<<dist[i]<<" ";
cout<<endl;*/
//minim=alot;
curr = Q.top().first;
Q.pop();
//if(dist[curr.id]==alot)
// break;
if(vizitat[curr])
continue;
/*for(i=1;i<=n;++i)
if(minim > dist[i] && !vizitat[i])
{
minim = dist[i];
minpoz = i;
}
if (minim == alot) //toate nodurile sunt unreachable
break;
vizitat[minpoz]=1;*/
vizitat[curr]=1;
for (i = 0; i<G[curr].vecini.end() - G[curr].vecini.begin();++i)
if(dist[curr] + G[curr].vecini[i].second < dist[G[curr].vecini[i].first])
{
dist[G[curr].vecini[i].first] = dist[curr] + G[curr].vecini[i].second;
Q.push(make_pair(G[curr].vecini[i].first, dist[G[curr].vecini[i].first]));
}
}
for (i=2;i<=n;++i)
{
if(dist[i]==alot)
h<<"0 ";
else
h<<dist[i]<<" ";
}
}