Submission #1519055
Source Code Expand
#include<bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; #define rep(i,n) for(int i=0;i<(int)(n);i++) #define reps(i,s,n) for(int i=(int)(s);i<(int)(n);i++) #define all(c) begin(c),end(c) const ll INF = 1e18; struct edge { ll from, to, cost; }; edge es[2000]; ll d[1000]; int V, E; //頂点、辺数 //頂点sからの最短d void bellmanford(int s) { rep(i, V)d[i] = INF; d[s] = 0; while (true) { bool update = false; rep(i, E) { edge e = es[i]; if (d[e.from] != INF&&d[e.to] > d[e.from] + e.cost) { d[e.to] = d[e.from] + e.cost; update = true; } } if (!update)break; } } //負の閉路->true bool find_negative_loop() { memset(d, 0, sizeof(d)); rep(i, V) { rep(j, E) { edge e = es[j]; if (d[e.to] > d[e.from] + e.cost) { d[e.to] = d[e.from] + e.cost; if (i == V - 1)return 0; } } } return false; } int main() { cin.sync_with_stdio(false); cin >> V >> E; rep(i, E) { int a, b, c; cin >> a >> b >> c; a--; b--; c = -c; es[i].from = a; es[i].to = b; es[i].cost = c; } if (find_negative_loop()) { cout << "inf" << endl; return 0; } bellmanford(0); cout << -d[V - 1] << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - Score Attack |
User | agis |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1261 Byte |
Status | TLE |
Exec Time | 2103 ms |
Memory | 256 KB |
Judge Result
Set Name | Sample | All | ||||||||
---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 400 | ||||||||
Status |
|
|
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 | 1 ms | 256 KB |
sample_02.txt | TLE | 2103 ms | 256 KB |
sample_03.txt | AC | 1 ms | 256 KB |
subtask_1_1.txt | AC | 1 ms | 256 KB |
subtask_1_10.txt | TLE | 2103 ms | 256 KB |
subtask_1_11.txt | TLE | 2103 ms | 256 KB |
subtask_1_12.txt | TLE | 2103 ms | 256 KB |
subtask_1_13.txt | AC | 1 ms | 256 KB |
subtask_1_14.txt | TLE | 2103 ms | 256 KB |
subtask_1_15.txt | TLE | 2103 ms | 256 KB |
subtask_1_16.txt | AC | 1 ms | 256 KB |
subtask_1_17.txt | AC | 1 ms | 256 KB |
subtask_1_18.txt | AC | 2 ms | 256 KB |
subtask_1_19.txt | AC | 3 ms | 256 KB |
subtask_1_2.txt | AC | 2 ms | 256 KB |
subtask_1_20.txt | AC | 1 ms | 256 KB |
subtask_1_21.txt | AC | 2 ms | 256 KB |
subtask_1_22.txt | AC | 4 ms | 256 KB |
subtask_1_23.txt | TLE | 2103 ms | 256 KB |
subtask_1_24.txt | AC | 3 ms | 256 KB |
subtask_1_25.txt | TLE | 2103 ms | 256 KB |
subtask_1_26.txt | AC | 2 ms | 256 KB |
subtask_1_27.txt | TLE | 2103 ms | 256 KB |
subtask_1_3.txt | AC | 2 ms | 256 KB |
subtask_1_4.txt | AC | 2 ms | 256 KB |
subtask_1_5.txt | TLE | 2103 ms | 256 KB |
subtask_1_6.txt | TLE | 2103 ms | 256 KB |
subtask_1_7.txt | AC | 2 ms | 256 KB |
subtask_1_8.txt | AC | 2 ms | 256 KB |
subtask_1_9.txt | AC | 1 ms | 256 KB |