Pagini recente » Cod sursa (job #1667426) | Cod sursa (job #2517379) | Cod sursa (job #1650619) | Rezultatele filtrării | Cod sursa (job #3302757)
#include <iostream>
#include<fstream>
#include<queue>
#include<vector>
using namespace std;ifstream fin("dijkstra.in");ofstream fout("dijkstra.out");struct qer{int x,y;};
struct comp{
bool operator()(qer a,qer b){return a.y<b.y;}
};
vector<qer>v[50001];priority_queue<qer,vector<qer>,comp>q;
int n,m,i,a,b,c,afis[50001],x,y,x1,y1;
int main()
{
fin>>n>>m;for(i=1;i<=m;i++){fin>>a>>b>>c;v[a].push_back({b,c});}
q.push({1,0});for(i=2;i<=n;i++)afis[i]=1e9;
while(!q.empty()){
x=q.top().x;y=q.top().y;q.pop();
for(i=0;i<v[x].size();i++)
{
x1=v[x][i].x;y1=v[x][i].y;
if(y+y1<afis[x1]){
afis[x1]=y+y1;q.push({x1,y+y1});
}
}
}for(i=2;i<=n;i++)fout<<afis[i]<<' ';
return 0;
}