Pagini recente » Cod sursa (job #2973496) | Cod sursa (job #1010028)
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#define infinit 1 << 30
using namespace std;
int n, m;
int minim[5010];
struct vecin
{
int v, dist;
vecin(int v = 0, int dist = 0):v(v), dist(dist)
{
}
};
struct cmp
{
bool operator()(int x, int y)
{
return minim[x] > minim[y];
}
};
vector<vecin> graf[50010];
priority_queue<int, vector<int>, cmp> q;
void citire()
{
scanf("%d%d", &n, &m);
int x, y, d;
for(int i = 0; i < m; i++)
{
scanf("%d%d%d", &x, &y, &d);
graf[x].push_back(vecin(y, d));
}
for(int i = 1; i <= n; i++)
minim[i] = infinit;
}
void rezolvare()
{
q.push(1);
int p, t, i;
while(!q.empty())
{
p = q.top();
q.pop();
for(i = 0; i < graf[p].size(); i++)
{
t = graf[p][i].v;
if(minim[p] + graf[p][i].dist < minim[t])
{
minim[t] = minim[p] + graf[p][i].dist;
q.push(t);
}
}
}
}
void afisare()
{
for(int i = 2; i <= n; i++)
{
if(minim[i] == infinit)
printf("0 ");
else printf("%d ", minim[i]);
}
}
int main()
{
freopen("dijkstra.in","r",stdin);
freopen("dijkstra.out","w", stdout);
citire();
rezolvare();
afisare();
return 0;
}
/*void citire_mat()
{
int x,y,val,i,j;
scanf("%d%d",&n,&m);
for(i=0;i<m;i++)
{
scanf("%d%d",&x,&y,&val);
mat[x][y]=val;
}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
if(mat[i][j]==0)
mat[i][j]=infinit;
if(i==j)
a[i][j]=0;
}
for(i=0;i<n;i++)
minim[i]=a[0][i];
viz[0]=true;
}*/