View Code of Problem 128

#include <stdio.h>

struct road
{
    int form;
    int to;
    int power;
}roadlist[20010];
 
struct node
{
    int value;
    int isInfinity;
}nodelist[1005];
 
int main()
{
    int n,m,i;
    while (scanf("%d%d",&n,&m)!=EOF)
    {
        for (i=0; i<m; i++)
        {
            scanf("%d%d%d",&roadlist[i].form,&roadlist[i].to,&roadlist[i].power);
        }
        for (i=2; i<=n; i++)
        {
            nodelist[i].isInfinity=1;
        }
         
        nodelist[1].value=0;
        nodelist[1].isInfinity=0;
         
        int flag = 1,run_time = 0,lasttargetvalue = 0;
        while (flag)
        {
            flag=0;
            run_time++;
            for (i=0; i<m; i++)
            {
                if (nodelist[roadlist[i].form].isInfinity)
                {
                    continue;
                }
                else if (nodelist[roadlist[i].to].isInfinity)
                {
                    nodelist[roadlist[i].to].value=nodelist[roadlist[i].form].value+roadlist[i].power;
                    nodelist[roadlist[i].to].isInfinity=0;
                    flag=1;
                }
                else
                {
                    if (nodelist[roadlist[i].to].value>nodelist[roadlist[i].form].value+roadlist[i].power)
                    {
                        nodelist[roadlist[i].to].value=nodelist[roadlist[i].form].value+roadlist[i].power;
                        flag=1;
                    }
                }
            }
            if (!nodelist[n].isInfinity && nodelist[n].value<0)
            {
                break;
            }
            else if (nodelist[n].isInfinity && run_time>=n)//如果在经历超过n-1次之后，目标点仍为∞
            {
                break;
            }
            else if (!nodelist[n].isInfinity && run_time==n-1)//在经历n-1次后，目标点有权值
            {
                lasttargetvalue=nodelist[n].value;
            }
            else if (!nodelist[n].isInfinity && run_time>=n)//在经历n次后，目标点有权值，则上一个判断必定保存了上一次的权值
            {
                if (lasttargetvalue>nodelist[n].value)//判断
                {
                    nodelist[n].value=-1;//直接赋值为-1，那不就一定能到了吗
                    break;
                }
                else
                {
                    break;
                }
            }
        }
        if (!nodelist[n].isInfinity && nodelist[n].value<0)
        {
            printf("YES\n");
        }
        else
        {
            printf("NO\n");
        }
    }
    return 0;
}