Pagini recente » Profil SlavicG | Cod sursa (job #314135) | Profil Bulanel | Atasamentele paginii Profil 4charlottee953ho3 | Cod sursa (job #759722)
Cod sursa(job #759722)
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
#define MAX 50005
#define INF 0xffffff
vector<pair<int,int> >g[MAX];
set<pair<int,int> >a;
int n,m,d[MAX];
void dijkstra(){
int c,x,y;
for(int i=2;i<=n;i++)d[i]=INF;
a.insert(make_pair(0,1));
while(s.size()>0)
{
c=a.begin()->first;
x=a.begin()->second;
a.erase(a.begin());
for(int i=0;i<g[x].size();i++)
{
y=g[x][i].second;
if(d[y]>c+g[x][i].first)
{
d[y]=c+g[x][i].first;
a.insert(make_pair(d[y],y));
}
}
}
}
int main(){
int c,x,y;
freopen("dijkstra.in","r",stdin);
freopen("dijkstra.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d %d %d",&x,&y,&c);
g[x].push_back(make_pair(c,y));
}
dijkstra();
for(int i=2;i<=n;i++)printf("%d ",d[i]==INF?0:d[i]);
return 0;
}