Submission #1609561

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
long long W[1010][1010];
long long dis[1010];
long long vertex,edge;
#define inf 10000000000
bool flag[1010];
void Bellman_fold(long long s)
{
    for(long long i=0;i<vertex;++i)
    {
        dis[i]=inf;
    }
    dis[s]=0;
    long long temp;

    for(long long i=1;i<vertex;++i)
    {
        for(long long j=0;j<vertex;++j)
        {
            for(long long k=0;k<vertex;++k)
            {
                if(dis[j]!=inf&&dis[j]+W[j][k]<dis[k])
                {
                    dis[k]=dis[j]+W[j][k];
                }
            }
        }
    }
    for(long long i=1;i<=vertex;++i)
    {
        for(long long j=0;j<vertex;++j)
        {
            for(long long k=0;k<vertex;++k)
            {
                if(flag[j]&&W[j][k]!=inf)
                {
                    flag[k]=true;
                }
                if(dis[j]!=inf&&dis[j]+W[j][k]<dis[k])
                {
                    dis[k]=dis[j]+W[j][k];
                    flag[k]=true;
                }
            }

        }
    }
}

int main(void)
{

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>vertex>>edge;
    fill(*W,*W+sizeof(W)/sizeof(long long),inf);
    long long from,to,weight;
    for (int i=0;i<edge;++i)
    {
        cin>>from>>to>>weight;
        W[--from][--to]=weight*(-1);
    }
//    for(long long i=0;i<vertex;++i)
//    {
//        for(long long j=0;j<vertex;++j)
//        {
//            cin>>weight;
//            W[i][j]=weight;
//        }
//    }
    Bellman_fold(0);
    if(!flag[vertex-1])
    {
        cout <<dis[vertex-1]*(-1)<<endl;
    }
    else
    {
        cout <<"inf"<<endl;
    }


    return 0;
}

Submission Info

Judge Result