Voltar

## Dijkstra - Grafos

0 Curtidas
```#include
#include
#define NN 1024

int d[NN], q[NN], inq[NN], prev[NN], qs;

#define CLR( x, v ) memset( x, v, sizeof( x ) )
#define BUBL {     t = q[i]; q[i] = q[j]; q[j] = t;     t = inq[q[i]]; inq[q[i]] = inq[q[j]]; inq[q[j]] = t; }

int dijkstra( int n, int s, int t )
{
CLR( d, 9 ); CLR( inq, -1 ); CLR( prev, -1 );
d[s] = qs = 0;
inq[q[qs++] = s] = 0;
prev[s] = -2;

while( qs )
{
// get the minimum from the q
int u = q[0]; inq[u] = -1;

// bubble down
q[0] = q[--qs];
if( qs ) inq[q[0]] = 0;
for( int i = 0, j = 2*i + 1, t; j < qs; i = j, j = 2*i + 1 )
{
if( j + 1 < qs && d[q[j + 1]] < d[j] ) j++;
if( d[q[j]] >= d[q[i]] ) break;
BUBL;
}

// relax neighbours
for( int k = 0, v = adj[u][k]; k < deg[u]; v = adj[u][++k] )
{
int newd = d[u] + graph[u][v];
if( newd < d[v] )
{
d[v] = newd;
prev[v] = u;
if( inq[v] < 0 ) { inq[q[qs] = v] = qs; qs++; }

// bubble up
for( int i = inq[v], j = i/2, t;
d[q[i]] < d[q[j]]; i = j, j = i/2 )
BUBL;
}
}
}

return d[t];
}

int main()
{
int n, m;
while( scanf( " %d %d\n", &n, &m ) == 2 )
{
memset( deg, 0, sizeof( deg ) );
while( m-- )
{
int u, v, w;
scanf( " %d %d %d", &u, &v, &w );
graph[u][v] = graph[v][u] = w;
}

int ans = dijkstra( n, 0, n - 1 );

printf( "%d\n", ans );
}
return 0;
}
```