#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 (heap[x], heap[smallest]);
                       index[heap[x]] = x;
                       index[heap[smallest]] = 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 = 0;
     min = dist[heap[1]];
     heap[1] = heap[heap_size];
     index[heap[heap_size]] = 1;
     heap_size --;
     min_heapfy (1);
     return min;
}
int judge (int x, int y)
{
    edge *p;
    p = ver[x].first;
    while (p && p->id != y)
    {
          p = p->next;
    }
    if (p)
    {
          return p->len;
    }
    else
    {
        return -1;
    }
}
bool empty ()
{
     return heap_size > 0 ? false : true;
}
void fixup (int id)
{
     int t1, t2;
     if (dist[id] < dist[heap[index[id]/2]])
     {
                  t1 = index[id]/2;
                  t2 = heap[index[id]/2];
                  heap[index[id]] = t2;
                  index[t2] = index[id];
                  index[id] = t1;
                  heap[t1] = id;
                  fixup (t2);
     }
}
int Dijkstra (int s)
{
     int t, tmp1, tmp2, j, v, w;
     visited[s] = true;
     while (!empty())
     {
         v = heap[1];
         visited[v] = true;
         if (v == (n - 1))
         {
               return dist[v];
         }
         extract_min ();
         for (j = 0; j < n; j ++)
         {
             if (!visited[j])
             {
                       w = judge (v, j);
                       if (dist[v] + w < dist[j] && w != -1)
                       {
                                   dist[j] = dist[v] + w;
                                   fixup (j);
                       }
             }
         }
     }
}
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;
}

• 最希望管理员能发给我一组有力的测试数据！！ (4096) 417370112 2007-02-09 22:44:07
• 现在变tle了！ (3522) 417370112 2007-02-10 12:37:36
• 187行……你也写得太长了吧…… (4096) rovingcloud 2007-02-10 13:17:06
• 经过４次RE,５次TLE,15次WA,两天的努力，终于把这个题目给AC了,忍不住发贴庆祝　！！！！ (3451) 417370112 2007-02-10 14:03:33
  • cong~~~ (3789) rovingcloud 2007-02-10 14:14:47