Pagini recente » Cod sursa (job #2769416) | Cod sursa (job #2560809) | Cod sursa (job #1883267)
#include <fstream>
#include <queue>
#include <vector>
#include <functional>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
#define INF 50000000
const int N=50000, M=250000;
vector<pair<int,int>> ad[N+1];
int n, m, d[N+1];
int main()
{
fin>>n>>m;
for(int i=0;i<m;i++)
{
int a, b, c;
fin>>a>>b>>c;
ad[a].push_back(make_pair(b, c));
}
for(int i=1;i<=n;i++)
d[i] = INF;
d[1] = 0;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
pq.push(make_pair(0, 1));
while(!pq.empty())
{
int p = pq.top().second;
pq.pop();
for(auto x : ad[p])
{
if (d[p]+x.second<d[x.first])
{
d[x.first]=d[p]+x.second;
pq.push(make_pair(d[x.first], x.first));
}
}
}
for(int i=2;i<=n;i++)
fout<<((d[i]==INF)?0:d[i])<<" ";
return 0;
}