Submission #1531574
Source Code Expand
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <stack>
#include <queue>
#include <functional>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <vector>
#include <array>
#include <tuple>
#include <utility>
#include <numeric>
#include <iomanip>
#include <cctype>
#include <cmath>
#include <assert.h>
#include <cstdlib>
#include <list>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using PII = pair<int, int>;
using PLL = pair<ll, ll>;
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {
return s << "(" << p.first << ", " << p.second << ")";
}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
s << "[";
for (int i = 0; i < v.size(); i++) s << (i == 0 ? "" : ", ") << v[i];
s << "]";
return s;
}
#define ALL(a) (a).begin(), (a).end()
using Weight = ll;
// 重み付きの辺
struct Edge {
int from, to;
Weight weight;
Edge() {}
Edge(int to) : from(-1), to(to), weight(-1) {}
Edge(int from, int to) : from(from), to(to), weight(-1) {}
Edge(int from, int to, Weight weight) : from(from), to(to), weight(weight) {}
bool operator<(const Edge& e) const {
return (weight != e.weight) ? (weight < e.weight) : (from < e.from);
}
bool operator>(const Edge& e) const {
return (weight != e.weight) ? (weight > e.weight) : (from > e.from);
}
};
using Arc = Edge;
using Graph = vector<vector<Edge>>;
using DGraph = vector<vector<Arc>>;
using Tree = Graph;
// 最初に初期化することを忘れないように!
using GArray = vector<Weight>;
using GMatrix = vector<GArray>;
// この4つの関数は頂点数を固定したバージョンでも動く
void add_edge(Graph& g, int u, int v, Weight w = -1) {
g[u].push_back(Edge(u, v, w));
g[v].push_back(Edge(v, u, w));
}
void add_arc(DGraph& dg, int u, int v, Weight w = -1) {
dg[u].push_back(Arc(u, v, w));
}
namespace BellmanFord {
DGraph dgraph;
int V;
vector<Weight> cost;
const Weight INF = (1LL << 50);
void initialize(DGraph& dg) {
V = dg.size();
dgraph = dg;
cost.resize(V);
}
// 負の閉路を見つけたらtrueを返す
bool solve(int s) {
for (int v = 0; v < V; v++) cost[v] = INF;
cost[s] = 0;
bool update = true;
for (int i = 0; i < V && update; i++) {
update = false;
for (int from = 0; from < V; from++) {
for (Arc& a : dgraph[from]) {
if (cost[a.from] != INF && cost[a.to] > cost[a.from] + a.weight) {
cost[a.to] = cost[a.from] + a.weight;
update = true;
}
}
}
if (i == V - 1 && update) return true;
}
return false;
}
};
int main() {
int N, M;
cin >> N >> M;
DGraph dgraph(N);
for (int i = 0; i < M; i++) {
int a, b, c;
cin >> a >> b >> c;
a--; b--;
add_arc(dgraph, a, b, -c);
}
BellmanFord::initialize(dgraph);
if (BellmanFord::solve(0)) cout << "inf" << endl;
else cout << -BellmanFord::cost[N - 1] << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
D - Score Attack |
User |
myusa |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
3458 Byte |
Status |
WA |
Exec Time |
8 ms |
Memory |
384 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 |
AC |
1 ms |
256 KB |
sample_03.txt |
AC |
1 ms |
256 KB |
subtask_1_1.txt |
AC |
2 ms |
256 KB |
subtask_1_10.txt |
AC |
1 ms |
256 KB |
subtask_1_11.txt |
AC |
2 ms |
256 KB |
subtask_1_12.txt |
AC |
5 ms |
384 KB |
subtask_1_13.txt |
AC |
1 ms |
256 KB |
subtask_1_14.txt |
AC |
5 ms |
384 KB |
subtask_1_15.txt |
AC |
8 ms |
384 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 |
384 KB |
subtask_1_19.txt |
AC |
3 ms |
384 KB |
subtask_1_2.txt |
AC |
2 ms |
384 KB |
subtask_1_20.txt |
AC |
1 ms |
256 KB |
subtask_1_21.txt |
AC |
2 ms |
384 KB |
subtask_1_22.txt |
AC |
3 ms |
384 KB |
subtask_1_23.txt |
WA |
1 ms |
256 KB |
subtask_1_24.txt |
AC |
3 ms |
384 KB |
subtask_1_25.txt |
WA |
3 ms |
256 KB |
subtask_1_26.txt |
AC |
4 ms |
384 KB |
subtask_1_27.txt |
WA |
5 ms |
384 KB |
subtask_1_3.txt |
AC |
2 ms |
384 KB |
subtask_1_4.txt |
AC |
2 ms |
384 KB |
subtask_1_5.txt |
AC |
2 ms |
256 KB |
subtask_1_6.txt |
AC |
4 ms |
384 KB |
subtask_1_7.txt |
AC |
2 ms |
384 KB |
subtask_1_8.txt |
AC |
2 ms |
384 KB |
subtask_1_9.txt |
AC |
1 ms |
256 KB |