Submission #1282514
Source Code Expand
#include <iostream>
#include <sstream>
#include <string>
#include <cassert>
#include <cmath>
#include <climits>
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <numeric>
#include <iomanip>
using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) ((int)v.size())
#define pb push_back
#define mp make_pair
#define mt make_tuple
// 頂点は0-originとする
template <typename T>
class BellmanFord {
struct edge {
int from;
int to;
T cost;
};
public:
T INF;
T NEGATIVE_INF;
BellmanFord(int V)
: INF(std::numeric_limits<T>::max())
, NEGATIVE_INF(std::numeric_limits<T>::min())
, m_V(V) {
m_es.clear();
}
void add_dir_edge(int from, int to, T cost) {
m_es.push_back( edge{from, to, cost} );
}
void add_undir_twoways(int v1, int v2, T cost) {
add_dir_edge(v1, v2, cost);
add_dir_edge(v2, v1, cost);
}
// 頂点sから各頂点までの距離を計算してdに格納
vector<T> shortest_path(int s)
{
// INF: その頂点には到達できない
// INF以外: sからの最短距離
vector<T> d(m_V, INF);
vector<char> has_negative_loop(m_V);
d[s] = 0;
REP(try_num, m_V) {
bool update = false;
REP(i, SIZE(m_es)) {
edge e = m_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 (try_num == m_V - 1) {
has_negative_loop[e.to] = 1;
}
}
}
if (!update) break;
}
// cout << "dists:" << endl;
// for (auto e: d) cout << e << " ";
// cout << endl;
// cout << "negative loop:" << endl;
// for (auto e: has_negative_loop) cout << int(e) << " ";
// cout << endl;
// negative loopがある頂点の最短路をNEGATIVE_INFに書き換える
REP(i, m_V) {
if (has_negative_loop[i]) d[i] = NEGATIVE_INF;
}
return move(d);
}
// sから各頂点までの最短路に閉路があるかを返す
bool find_negative_loop_from_v(int s) {
vector<T> d(m_V, INF);
d[s] = 0;
// ループの実行は高々|V|-1回のはず
// ループの実行回数が|V|よりも大きければ閉路があったとみなす
int count = 0;
while (true) {
bool update = false;
REP(i, SIZE(m_es)) {
edge e = m_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;
++count;
if (count > m_V) return true;
}
return false;
}
// グラフ全体のどこかに負の経路があることを検出
bool find_negative_loop_somewhere(void) {
vector<T> d(m_V);
REP(i, SIZE(d)) {
REP(j, SIZE(m_es)) {
edge e = m_es[j];
if (d[e.to] > d[e.from] + e.cost){
d[e.to] = d[e.from] + e.cost;
// n回目にも更新があるなら負の経路が存在する
if (i == SIZE(d) - 1) {
return true;
}
}
}
// for(int i = 0; i < SIZE(d); ++i) {
// cout << d[i] << ", ";
// }
// cout << endl;
}
return false;
}
private:
int m_V;
vector<edge> m_es;
};
int main(void)
{
cin.sync_with_stdio(false);
int N, M;
cin >> N >> M;
BellmanFord<ll> bf(N);
REP(m, M) {
ll a, b, c;
cin >> a >> b >> c;
--a; --b;
bf.add_dir_edge(a, b, -c);
}
auto dists = bf.shortest_path(0);
if (dists[N-1] == bf.NEGATIVE_INF) {
cout << "inf" << endl;
}
else {
cout << -dists[N-1] << endl;
}
return 0;
}
Submission Info
Submission Time |
|
Task |
D - Score Attack |
User |
minus9d |
Language |
C++14 (GCC 5.4.1) |
Score |
400 |
Code Size |
4719 Byte |
Status |
AC |
Exec Time |
5 ms |
Memory |
384 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
400 / 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 |
1 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 |
3 ms |
384 KB |
subtask_1_13.txt |
AC |
1 ms |
256 KB |
subtask_1_14.txt |
AC |
3 ms |
256 KB |
subtask_1_15.txt |
AC |
5 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 |
256 KB |
subtask_1_19.txt |
AC |
2 ms |
384 KB |
subtask_1_2.txt |
AC |
1 ms |
256 KB |
subtask_1_20.txt |
AC |
1 ms |
256 KB |
subtask_1_21.txt |
AC |
1 ms |
256 KB |
subtask_1_22.txt |
AC |
2 ms |
384 KB |
subtask_1_23.txt |
AC |
1 ms |
256 KB |
subtask_1_24.txt |
AC |
2 ms |
384 KB |
subtask_1_25.txt |
AC |
2 ms |
256 KB |
subtask_1_26.txt |
AC |
1 ms |
256 KB |
subtask_1_27.txt |
AC |
4 ms |
256 KB |
subtask_1_3.txt |
AC |
1 ms |
256 KB |
subtask_1_4.txt |
AC |
1 ms |
256 KB |
subtask_1_5.txt |
AC |
2 ms |
256 KB |
subtask_1_6.txt |
AC |
4 ms |
256 KB |
subtask_1_7.txt |
AC |
1 ms |
256 KB |
subtask_1_8.txt |
AC |
1 ms |
256 KB |
subtask_1_9.txt |
AC |
1 ms |
256 KB |