Pagini recente » Cod sursa (job #1675464) | Cod sursa (job #704464)
Cod sursa(job #704464)
#include <cstdio>
#include <vector>
#include <queue>
#define N 50001
#define I 999999999
using namespace std;
struct nod
{
int v;
int c;
};
int n;
int d[N];
bool viz[N];
struct cmp
{
bool operator () (const int &a, const int &b) const
{
return d[a] > d[b];
}
};
vector < nod > g[N];
priority_queue < int, vector < int >, cmp> q;
void citire()
{
freopen ("dijkstra.in", "r", stdin);
int m;
scanf ("%d %d ", &n, &m);
while (m --)
{
int v;
nod a;
scanf ("%d %d %d ", &v, &a.v, &a.c);
g[v].push_back (a);
swap (v, a.v);
g[v].push_back (a);
}
}
void inceput(int vf)
{
for (int i = 1; i <= n; ++ i)
d[i] = I;
unsigned int m = g[vf].size();
for (unsigned int i = 0; i < m; ++ i)
d[g[vf][i].v] = g[vf][i].c;
for (int i = 1; i <= n; ++ i)
q.push (i);
viz[vf] = 1;
d[vf] = 0;
}
void dijkstra(int vf)
{
inceput(vf);
while (!q.empty())
{
while (!q.empty() && viz[q.top()])
q.pop();
if (q.empty())
return;
int v = q.top();
q.pop();
viz[v] = 1;
unsigned int m = g[v].size();
for (unsigned int i = 0; i < m; ++ i)
{
nod aux = g[v][i];
if (!viz[aux.v] && d[v] + aux.c < d[aux.v])
{
d[aux.v] = d[v] + aux.c;
q.push (aux.v);
}
}
}
}
void afisare()
{
freopen ("dijkstra.out", "w", stdout);
for (int i = 2; i <= n; ++ i)
printf ("%d ", d[i]);
printf ("\n");
}
int main()
{
citire();
dijkstra(1);
afisare();
return 0;
}