Pagini recente » Borderou de evaluare (job #2237879) | Cod sursa (job #1131425)
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
#define NMAX 50010
#define oo (1<<30)
#define PKnoten first
#define PAbstand second
int N,M;
vector < int > Abstand;
vector < pair < int , int > > G[NMAX];
priority_queue < pair < int , int > , vector < pair < int , int > > , greater < pair < int , int > > > PQ;
void Scannen()
{
freopen("dijkstra.in","r",stdin);
scanf("%d%d",&N,&M);
for(int i=1,x,y,z;i<=M;i++)
{
scanf("%d%d%d",&x,&y,&z);
G[x].push_back(make_pair(y,z));
}
}
void Losen_Dijkstra()
{
Abstand.resize(N+1);
for(int i=2;i<=N;Abstand[i++]=oo);
PQ.push(make_pair(1,0));
while(!PQ.empty())
{
int _Knoten = PQ.top().PKnoten;
int _Abstand = PQ.top().PAbstand;
PQ.pop();
for(vector < pair < int , int > > :: iterator it = G[_Knoten].begin(); it != G[_Knoten].end(); ++ it )
if(Abstand[(*it).PKnoten] > _Abstand + (*it).PAbstand)
{
Abstand[(*it).PKnoten] = _Abstand + (*it).PAbstand;
PQ.push(make_pair( (*it).PKnoten , Abstand[(*it).PKnoten]) );
}
}
}
void Drucken()
{
freopen("dijkstra.out","w",stdout);
for(int i=2;i<=N;i++)
if(Abstand[i] != oo)
printf("%d ",Abstand[i]);
else
printf("0 ");
}
int main()
{
Scannen();
Losen_Dijkstra();
Drucken();
return 0;
}