这题涉及负权，必须使用Bellman-Ford。我们可以先使用传递闭包判断各种可达性，然后使用Bellman-Ford，注意，因为这题在路途中不可以有负数，所以只需要松弛那些没有负权的dist，而且还需使用已经计算好的传递闭包结果判断松弛的点能否可达1和N。
在最后，如果松弛的次数大于等于N，或者dist[N]>0，则成功。
建议大家看看这题那个“无奈的来看看”的帖子，那里有比较悲催的数据，过了那些这题就基本过了。
Bellman-Ford代码：
int Bellman_Ford(int a,int b)
{
    for(int i=1;i<=N;i++) d[i]=-100000000;
    d[a]=100;
    int tot=0;
    for(int I=1;I<=N;I++)
    {
        bool flag=0;
        for(int i=1;i<=N;i++)
            for(edge *p=S[i];p;p=p->next)
                if(d[i]+p->len>d[p->num] && can[p->num][N] && can[1][p->num] && d[i]>0)
                {
                    d[p->num]=d[i]+p->len;
                    flag=1;
                }
        if(flag) tot++;
        else break;
    }
    if(d[b]>0 || tot>=N)
        return 1;
    else
        return 0;
}

• Re:Bellman-Ford算法 (14) 13110572050 2015-01-20 16:30:48