Uva开始比赛了，把我的代码先给你看看吧.....

// Solution by richard
// shortest path problem,courtesy of Dijkstra

#include <stdio.h>
#include <string.h>

struct node
{
  int vto,v;
  int next;
};

struct edge
{
  int s,t;
  int v;
};

struct node matrix[1<<18];
struct edge heap[1<<18];
int d[65536/2],visit[65536/2];
int tail=0;
int bi;
int n,m;

void fix_up()
{
  int i,k;
  struct edge p;

  i=tail;
  p=heap[i];
  while (i>1) {
    k=i/2;
    if (heap[k].v>p.v) heap[i]=heap[k];
    else break;
    i=k;
  }
  heap[i]=p;
}

void fix_down()
{
  int i,k;
  struct edge p;
  
  i=1;
  p=heap[1];
  while (i<=tail/2) {
    k=i*2;
    if (k<tail && heap[k+1].v<heap[k].v) ++k;
    heap[i]=heap[k];
    i=k;
  }
  heap[i]=p;
}

void insert(int s,int t,int v)
{
  heap[++tail].s=s;
  heap[tail].t=t;
  heap[tail].v=v;
  fix_up();
}

struct edge get()
{
  struct edge p=heap[1];

  heap[1]=heap[tail--];
  fix_down();
  return p;
}

void construct(int s,int t,int v)
{
  matrix[bi].next=matrix[s].next;
  matrix[s].next=bi;
  matrix[bi].vto=t;
  matrix[bi++].v=v;
}

void get_edges(int s)
{
  int i;

  i=matrix[s].next;
  while (i) {
    insert(s,matrix[i].vto,matrix[i].v);
    i=matrix[i].next;
  }
}

void read_data()
{
  int i;
  int a,b,c;

  for (i=0;i<m;++i) {
    scanf("%d %d %d",&a,&b,&c);
    construct(a,b,c);
  }
}

void solve()
{
  struct edge e;

  visit[1]=1;
  get_edges(1);
  while (tail) {
    e=get();
    if (!visit[e.t]) {
      visit[e.t]=1;
      get_edges(e.t);
      d[e.t]=d[e.s]+e.v;
    }
  }
  
  printf("%d\n",d[n]);
}

int main()
{
  scanf("%d %d",&n,&m);
  bi=n+1;
  read_data();
  solve();
  return 0;
}

• Re:为什么老是wa，罪过啊。附上代码请强人帮忙看看，谢谢！ (2084) badboy 2007-01-20 23:12:32
  • 正确答案是4,我的代码发给你了 (0) TopBoy 2007-01-21 10:17:20