#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

const int MAXN = 30010;
const int MAXM = 155000;
const int INF = 0x7fffffff;

struct Edge
{
  int to;
  int val;
  Edge *next;
}e[MAXM], *hd[MAXN];

int m,n;
int idx;
int a[MAXN];
int b[MAXN];
int c[MAXN];
int q[MAXN];

void addEdge(int from,int to,int val)
{
  e[idx].to=to;
  e[idx].val=val;
  e[idx].next=hd[from];
  hd[from]=&e[idx++];
}
void makeGraph()
{
  memset(hd,0,sizeof(hd));
  idx=0;
  int i;
  for(i=1;i<=m;i++)
  addEdge(a[i],b[i],c[i]);
}

int d[MAXN];
int used[MAXN];
char mark[MAXN];

bool spfa()
{
  int head,tail,i,pos;
  Edge *p;
  head=tail=0;
  for(i=1;i<=n;i++)
  {
    mark[i]=0;
    used[i]=0;
    d[i]=INF;
  }
  d[1]=0;
  mark[1]=1;
  q[tail++]=1;
  while(head!=tail)
  {
    pos=q[head++];
    if(head==MAXN)
    head=0;
    mark[pos]=0;
    for(p=hd[pos];p!=0;p=p->next)
    if(d[p->to]>d[pos]+p->val)
    {
      d[p->to]=d[pos]+p->val;
      if(mark[p->to]==0)
      {
        mark[p->to]=1;
        q[tail++]=p->to;
        if(tail==MAXN)
        tail=0;
        used[p->to]++;
        if(used[p->to]==n)
        return false;
      }
    }
  }
  return true;
}

int main()
{
  int i;
  scanf("%d%d",&n,&m);
  for(i=1;i<=m;i++)
  scanf("%d%d%d",&a[i],&b[i],&c[i]);
  makeGraph();
  spfa();
  printf("%d\n",d[n]);
  return 0;
}

• Re:用spfa加队列的怎么就wa了呢，哪位好心的大牛知道的麻烦给发个邮件 (101) romanzhg 2010-11-21 15:23:14
  • Re:用spfa加队列的怎么就wa了呢，哪位好心的大牛知道的麻烦给发个邮件 (27) acm_bone 2010-11-21 21:06:39
• Re:用spfa加队列的怎么就wa了呢，哪位好心的大牛知道的麻烦给发个邮件 (104) 2guangnian 2011-01-29 23:07:42