Pagini recente » Cod sursa (job #1423167) | Cod sursa (job #2847704) | Cod sursa (job #1548574) | Cod sursa (job #3122527) | Cod sursa (job #1923394)
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
class Compare
{
public:
bool operator () (pair<int,int> &x,pair<int,int> &y)
{
return x.second<y.second;
}
};
vector < pair <int,int > > v[50001];
int dist[50001];
bool viz[50001];
priority_queue < pair<int,int> ,vector< pair <int,int> >, Compare > H;
void Dijkstra (int S)
{
int j;
dist[S]=0;
H.push(make_pair(S,dist[S]));
while (H.empty()==false)
{
int K=H.top().first;
H.pop();
if (viz[K]==false)
{
viz[K]=true;
for (j=0; j<v[K].size(); j++)
{
if (dist[v[K][j].first]>dist[K]+v[K][j].second&&viz[v[K][j].first]==false)
{
dist[v[K][j].first]=dist[K]+v[K][j].second;
H.push(make_pair(v[K][j].first,-dist[v[K][j].first]));
}
}
}
}
}
int main()
{
freopen ("dijkstra.in","r",stdin);
freopen ("dijkstra.out","w",stdout);
int n,m,i;
int A,B,C;
scanf ("%d %d",&n,&m);
for (i=1; i<=n; i++)
{
dist[i]=2000000000;
}
for (i=1; i<=m; i++)
{
scanf ("%d %d %d",&A,&B,&C);
v[A].push_back(make_pair(B,C));
}
Dijkstra(1);
for (i=2; i<=n; i++)
{
if (dist[i]==2000000000)
{
printf ("0 ");
}
else
{
printf ("%d ",dist[i]);
}
}
printf ("\n");
return 0;
}