Pagini recente » Cod sursa (job #26342) | Cod sursa (job #2209060)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
#define f first
#define s second
struct adat
{
bool l;
int hossz=99999999999;
vector<pair<int,int>>ut;
};
struct uthossz
{
int hova, ut;
};
uthossz q;
bool operator< (const uthossz &a, const uthossz &b)
{
return a.ut>b.ut;
}
long long n,m,a,b,c,i;
int main()
{
cin>>n>>m;
vector<adat>x(n+1);
for(i=1;i<=m;++i)
{
cin>>a>>b>>c;
x[a].ut.push_back({b,c});
//x[b].ut.push_back({a,c});
}
priority_queue<uthossz>que;
que.push({1,0});
while(!que.empty())
{
q=que.top();
while(x[q.hova].l)
{
que.pop();
q=que.top();
}
que.pop();
x[q.hova].l=true;
x[q.hova].hossz=q.ut;
for(auto e : x[q.hova].ut)
if(!x[e.f].l && x[e.f].hossz>(e.s+x[q.hova].hossz))
{
x[e.f].hossz=e.s+x[q.hova].hossz;
que.push({e.f,x[e.f].hossz});
}
}
for(i=2;i<=n;++i) cout<<x[i].hossz<<" ";
return 0;
}