Submission #1280899


Source Code Expand

using System;
using System.Text;
using System.Collections.Generic;
using System.Linq;
class Solve{
    public Solve(){}
    StringBuilder sb;
    public static int Main(){
        new Solve().Run();
        return 0;
    }
    void Run(){
        sb = new StringBuilder();
        Calc();
        Console.Write(sb.ToString());
    }
    void Calc(){
        string[] str = Console.ReadLine().Split(' ');
        int N = int.Parse(str[0]);
        int M = int.Parse(str[1]);
        int[] f = new int[M];
        int[] t = new int[M];
        long[] c = new long[M];
        for(int i=0;i<M;i++){
            str = Console.ReadLine().Split(' ');
            f[i] = int.Parse(str[0]) - 1;
            t[i] = int.Parse(str[1]) - 1;
            c[i] = int.Parse(str[2]);
        }
        BellmanFord B = new BellmanFord(f,t,c,N,0,100000000000000,N-1);
        if(B.NegativeCycle()){
            sb.Append("inf\n");
        }
        else{
            sb.Append(B.GetCost(N-1)+"\n");
        }
    }
}
class BellmanFord{
    bool NEGATIVECYCLE;
    long[] cost;
    public BellmanFord(int[] f,int[] t,long[] c,int n,int s,long INF,int G){
        cost = new long[n];
        int e = f.Length;
        for(int i=0;i<n;i++){
            cost[i] = -INF;
        }
        cost[s] = 0;
        for(int i=0;i<n;i++){
            for(int j=0;j<e;j++){
                if(cost[f[j]] != -INF){
                    cost[t[j]] = Math.Max(cost[t[j]],cost[f[j]]+c[j]);
                }
            }
        }
        long GC = cost[G];
        for(int i=0;i<n+1;i++){
            for(int j=0;j<e;j++){
                if(cost[f[j]] != -INF){
                    cost[t[j]] = Math.Max(cost[t[j]],cost[f[j]]+c[j]);
                }
            }
        }
        NEGATIVECYCLE = cost[G] != GC;
    }
    public bool NegativeCycle(){
        return NEGATIVECYCLE;
    }
    public long GetCost(int v){
        return cost[v];
    }
}

Submission Info

Submission Time
Task D - Score Attack
User leign
Language C# (Mono 4.6.2.0)
Score 400
Code Size 1989 Byte
Status AC
Exec Time 44 ms
Memory 13268 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 3
AC × 30
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_2.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt
Case Name Status Exec Time Memory
sample_01.txt AC 21 ms 11220 KB
sample_02.txt AC 20 ms 11092 KB
sample_03.txt AC 20 ms 11220 KB
subtask_1_1.txt AC 23 ms 9172 KB
subtask_1_10.txt AC 19 ms 11092 KB
subtask_1_11.txt AC 22 ms 11220 KB
subtask_1_12.txt AC 33 ms 11200 KB
subtask_1_13.txt AC 21 ms 11204 KB
subtask_1_14.txt AC 32 ms 11196 KB
subtask_1_15.txt AC 44 ms 13220 KB
subtask_1_16.txt AC 20 ms 9172 KB
subtask_1_17.txt AC 20 ms 9172 KB
subtask_1_18.txt AC 29 ms 11200 KB
subtask_1_19.txt AC 38 ms 11200 KB
subtask_1_2.txt AC 33 ms 11196 KB
subtask_1_20.txt AC 20 ms 11204 KB
subtask_1_21.txt AC 30 ms 11204 KB
subtask_1_22.txt AC 44 ms 11172 KB
subtask_1_23.txt AC 20 ms 11220 KB
subtask_1_24.txt AC 34 ms 11200 KB
subtask_1_25.txt AC 25 ms 13268 KB
subtask_1_26.txt AC 34 ms 11196 KB
subtask_1_27.txt AC 33 ms 9148 KB
subtask_1_3.txt AC 27 ms 9172 KB
subtask_1_4.txt AC 33 ms 11196 KB
subtask_1_5.txt AC 24 ms 9044 KB
subtask_1_6.txt AC 32 ms 11196 KB
subtask_1_7.txt AC 32 ms 11220 KB
subtask_1_8.txt AC 33 ms 11196 KB
subtask_1_9.txt AC 20 ms 9172 KB