#include <iostream>
#include <fstream>
#include <cstdio>
const int N = 31000;

using namespace std;

struct edge
{
       int id, len;
       edge *next;
};
struct vertex
{
       edge *first;
};

vertex ver[N];
int n, m, heap_size, dist[N], index[N], heap[2*N];
bool visited[N];

int left (int i)
{
    return 2*i;
}
int right (int i)
{
    return 2*i + 1;
}
int parent (int i)
{
    return i/2;
}
void swap (int &a, int &b)
{
     int t;
     t = a;
     a = b;
     b = t;
}
void min_heapfy (int x)
{
     int l, r, smallest = x;
     if (x >= 1 && x <= heap_size)
     {
          l = left (x);
          r = right (x);
          if (l <= heap_size && dist[heap[l]] < dist[heap[smallest]])
          {
                smallest = l;
          }
          if (r <= heap_size && dist[heap[r]] < dist[heap[smallest]])
          {
                smallest = r;
          }
          if (smallest != x)
          {
                       swap (index[heap[x]], index[heap[smallest]]);
                       swap (heap[x], heap[smallest]);
                       min_heapfy (smallest);
          }
     }
}
void build_heap ()
{
     int i;
     for (i = heap_size/2; i >= 1; i --)
     {
         min_heapfy (i);
     }
}
int extract_min ()
{
     int min;
     min = dist[heap[1]];
     heap[1] = heap[heap_size];
     index[heap[heap_size]] = 1;
     heap_size --;
     min_heapfy (1);
     return min;
}
bool empty ()
{
     return heap_size > 0 ? false : true;
}
void increase (int i)
{
     int j;
     j = i / 2;
     while (i >= 1 && j > 0 && dist[heap[i]] < dist[heap[j]])
     {
           swap (index[heap[i]], index[heap[j]]);
           swap (heap[i], heap[j]);
           i = j;
           j = i / 2;
     }
}
int Dijkstra (int s)
{
     int t, tmp1, tmp2, j, v, w;
     edge *p;
     visited[s] = true;
     while (!empty())
     {
         v = heap[1];
         visited[v] = true;
         if (v == (n - 1))
         {
               return dist[v];
         }
         extract_min ();
         p = ver[v].first;
         while (p)
         {
               if (!visited[p->id])
               {
                                   j = p->id;
                                   w = p->len;
                                   if (dist[v] + w < dist[j])
                                   {
                                               dist[j] = dist[v] + w;
                                               increase (index[j]);
                                   }
               }
               p = p->next;
         }
     }
}
void solve ()
{
     int i = 0;
     heap_size = n - 1;
     edge *p;
     p = ver[0].first;
     while (p)
     {
           dist[p->id] = p->len;
           p = p->next;
     }
     dist[0] = 0;
     build_heap ();
     printf ("%d\n", Dijkstra (0));
}
int main ()
{
    int i, a, b, c;
    edge *p;
    scanf ("%d %d", &n, &m);
    for (i = 0; i < n; i ++)
    {
        ver[i].first = NULL;
        visited[i] = false;
        heap[i] = i;
        index[i] = i;
        dist[i] = INT_MAX;
    }
    for (i = 0; i < m; i ++)
    {
        scanf ("%d %d %d", &a, &b, &c);
        p = new edge;
        p->id = b - 1;
        p->len = c;
        p->next = ver[a - 1].first;
        ver[a - 1].first = p;
    }
    solve ();
    return 0;
}

• cong~~~ (3789) rovingcloud 2007-02-10 14:14:47