Submission #1521582


Source Code Expand

#include <iostream>
#include <vector>
#define ll long long
#define INF 100000000000000000
#define MAX 100010
using namespace std;

struct edge{
  int to;
  ll cost;
};

typedef pair<ll, int> p;
vector<edge> graph[MAX];
vector<ll> dist;

bool bellman_ford(int n, int s){ //nは頂点数、sは開始頂点
  dist = vector<ll>(n, INF); //distをINFで初期化
  dist[s] = 0;
  for(int i = 0; i < n; i++){
    for(int v = 0; v < n; v++){
      for(int k = 0; k < graph[v].size(); k++){
        edge e = graph[v][k];
        if(dist[v] != INF && dist[e.to] > dist[v] + e.cost){
          dist[e.to] = dist[v] + e.cost;
          if(i == n - 1) return true; // 負の回路が存在
        }
      }
    }
  }
  return false;
}

int main(){
  int v, e, r, s, t;
  ll d;
  cin >> v >> e;
  for(int i = 0; i < e; i++){
    cin >> s >> t >> d;
    d = d * (-1);
    s--; t--;
    graph[s].push_back((edge){t, d});
  }
  bool check = bellman_ford(v, 0);
  if(check){
    cout << "inf" << endl;
  }else{
    cout << -1 * dist[v-1] << endl;
  }
  return 0;
}

Submission Info

Submission Time
Task D - Score Attack
User swkfn
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1101 Byte
Status WA
Exec Time 9 ms
Memory 2688 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 400
Status
AC × 3
AC × 27
WA × 3
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 2 ms 2560 KB
sample_02.txt AC 2 ms 2560 KB
sample_03.txt AC 2 ms 2560 KB
subtask_1_1.txt AC 3 ms 2560 KB
subtask_1_10.txt AC 2 ms 2560 KB
subtask_1_11.txt AC 3 ms 2560 KB
subtask_1_12.txt AC 6 ms 2688 KB
subtask_1_13.txt AC 4 ms 2560 KB
subtask_1_14.txt AC 6 ms 2688 KB
subtask_1_15.txt AC 9 ms 2688 KB
subtask_1_16.txt AC 2 ms 2560 KB
subtask_1_17.txt AC 2 ms 2560 KB
subtask_1_18.txt AC 5 ms 2688 KB
subtask_1_19.txt AC 8 ms 2688 KB
subtask_1_2.txt AC 5 ms 2688 KB
subtask_1_20.txt AC 4 ms 2560 KB
subtask_1_21.txt AC 5 ms 2560 KB
subtask_1_22.txt AC 9 ms 2688 KB
subtask_1_23.txt WA 2 ms 2560 KB
subtask_1_24.txt AC 6 ms 2688 KB
subtask_1_25.txt WA 4 ms 2560 KB
subtask_1_26.txt AC 6 ms 2688 KB
subtask_1_27.txt WA 6 ms 2688 KB
subtask_1_3.txt AC 4 ms 2560 KB
subtask_1_4.txt AC 6 ms 2688 KB
subtask_1_5.txt AC 4 ms 2560 KB
subtask_1_6.txt AC 6 ms 2688 KB
subtask_1_7.txt AC 5 ms 2560 KB
subtask_1_8.txt AC 5 ms 2688 KB
subtask_1_9.txt AC 2 ms 2560 KB