Submission #1609040


Source Code Expand

# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
using namespace std;
using LL = long long;
constexpr long long MOD = 1000000000 + 7;
constexpr long long INF = 100000000000;
const double PI = acos(-1);
 
struct edge { LL from, to, cost; };
edge es[2010];
 
LL d[2010];
bool negative[2010];
int v, e;
LL shortest_path(int s) {
	for (int i = 0; i < v; i++)d[i] = INF;
	d[s] = 0;
	for (int loop = 0; loop < v; loop++) {
		for (int i = 0; i < e; i++) {
			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;
			}
		}
	}
	return d[v];
}
int main() {
	cin >> v >> e;
	LL a[2010], b[2010], c[2010];
	for (int i = 0; i < e; i++) {
		cin >> a[i] >> b[i] >> c[i];
		c[i] = -c[i];
		es[i] = { a[i],b[i],c[i] };
	}
	LL ans = shortest_path(1);
	for (int loop = 0; loop < v; loop++) {
		for (int i = 0; i < e; i++) {
			if (d[a[i]] == INF) continue;
 
			if (d[b[i]] > d[a[i]] + c[i]) {
				d[b[i]] = d[a[i]] + c[i];
				negative[b[i]] = true;
 
			}
 
			if (negative[a[i]] == true) {
				negative[b[i]] = true;
 
			}
 
		}
 
 
	}
	if (negative[v]) {
		cout << "inf" << endl;
	}
	else {
		cout << -ans << endl;
	}
}

Submission Info

Submission Time
Task A - Between Two Integers
User M3_cp
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1428 Byte
Status WA
Exec Time 1 ms
Memory 256 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 100
Status
WA × 3
WA × 10
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_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt
Case Name Status Exec Time Memory
sample_01.txt WA 1 ms 256 KB
sample_02.txt WA 1 ms 256 KB
sample_03.txt WA 1 ms 256 KB
subtask_1_1.txt WA 1 ms 256 KB
subtask_1_2.txt WA 1 ms 256 KB
subtask_1_3.txt WA 1 ms 256 KB
subtask_1_4.txt WA 1 ms 256 KB
subtask_1_5.txt WA 1 ms 256 KB
subtask_1_6.txt WA 1 ms 256 KB
subtask_1_7.txt WA 1 ms 256 KB