程序如下，SPFA被注释了。
#include <cstdio>
#include <cstring>
#define oo 2147483647
#define maxn 10001
#define maxm 31111

using namespace std;

struct edge_type
{
    int x,y,cost,next;
};

int n,m,total;
bool mark[maxn + 1];
int stack[maxn + 1];
int dist[maxn + 1];

int first[maxn + 1];
edge_type g[maxm + 1];

void add(int x,int y,int cost)
{
    g[++total].x = x; g[total].y = y; g[total].cost = cost;
    g[total].next = first[x];
    first[x] = total;
}

void spfa()
{
    memset(mark,0,sizeof(mark));
    memset(dist,0,sizeof(dist));
    for (int i=1;i<=n;i++){ //这段是BellmanFord
        bool flag = 0;
        for (int j=1;j<=total;j++){
            int x = g[j].x,y = g[j].y,c = g[j].cost;
            if (dist[x] + c>dist[y]){
                dist[y] = dist[x] + c;
                flag = 1;
            }
        }
        if (!flag) break;
    }
    /* SPFA在这里
    int top = 1;
    for (top=1;top<=n + 1;top++){
        stack[top] = top - 1;
    }
    while (top){
        int x = stack[top --];
        mark[x] = 0;
        for (int temp=first[x];temp;temp=g[temp].next){
            int y = g[temp].y;
            int tmp;
            if ((tmp = dist[x] + g[temp].cost)>dist[y]){
                dist[y] = tmp;
                if (!mark[y]){
                    mark[y] = 1;
                    stack[++top] = y;
                }
            }
        }
    } */
    /*
    for (int i=1;i<=n;i++){
        printf("%d ",dist[i]);
    }
    printf("\n");
   */ 
}

int main()
{
    freopen("1716.in","r",stdin);
    freopen("1716.out","w",stdout);
    while (scanf("%d",&m)==1){
        total = 0;
        memset(first,0,sizeof(first));
        n = 0;
        for (int i=1;i<=m;i++){
            int a,b;
            scanf("%d%d",&a,&b);
            b ++;
            if (a>b){
                int tmp = a; a = b; b = tmp;
            }
            if (b>n) n = b;
            add(a,b,2);
        }
        for (int i=0;i<=n;i++){
            add(i,i + 1,0);
            add(i + 1,i,-1);
        }
        spfa();
        printf("%d\n",dist[n]);
    }
}

• 同求 直接扒1201代码SPFA WA, bellman AC (0) allen4053040allen 2011-02-10 23:02:51
• dist初值应设为-1或更小 (2351) NKHelloWorld 2011-08-02 18:47:08