Submission #1284138
Source Code Expand
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <sstream>
#include <iostream>
#include <iomanip>
#define _USE_MATH_DEFINES
#include <cmath>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cfloat>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <cassert>
using namespace std;
#define EPS 1e-12
#define ull unsigned long long
#define ll long long
#define VI vector<ll>
#define PII pair<ll, ll>
#define VVI vector<vector<ll> >
#define REP(i,n) for(int i=0,_n=(n);(i)<(int)_n;++i)
#define RANGE(i,a,b) for(int i=(int)a,_b=(int)(b);(i)<_b;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define ALLR(c) (c).rbegin(), (c).rend()
#define PB push_back
#define MP(a, b) make_pair(a, b)
#define POPCOUNT __builtin_popcount
#define POPCOUNTLL __builtin_popcountll
#define CLEAR(table, v) memset(table, v, sizeof(table));
#define PRINT1(table, D0) REP(d0, D0) cout<<table[d0]<<" "; cout<<"\n";
#define PRINT2(table, D0, D1) REP(d0, D0) { REP(d1, D1) cout<<table[d0][d1]<<" "; cout<<"\n"; }
#define PRINT3(table, D0, D1, D2) REP(d0, D0) { REP(d1, D1) { REP(d2, D2) cout<<table[d0][d1][d2]<<" "; cout<<"\n"; } cout<<"\n"; }
#define UNIFORM_DOUBLE(a, b) (((b-a)*(double)rand()/RAND_MAX)+a) // [a, b)
#define UNIFORM_LL(a, b) (ll)UNIFORM_DOUBLE(a, b) // [a, b)
#define IN(v, lo, hi) ((lo)<=(v) && (v)<(hi))
#define DD(v) cout<<#v<<": "<<v<<endl
template <typename T0, typename T1> std::ostream& operator<<(std::ostream& os, const map<T0, T1>& v) { for( typename map<T0, T1>::const_iterator p = v.begin(); p!=v.end(); p++ ){os << p->first << ": " << p->second << " ";} return os; }
template <typename T0, typename T1> std::ostream& operator<<(std::ostream& os, const pair<T0, T1>& v) { os << v.first << ": " << v.second << " "; return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const vector<T>& v) { for( int i = 0; i < (int)v.size(); i++ ) { os << v[i] << " "; } return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const vector<vector<T> >& v) { for( int i = 0; i < (int)v.size(); i++ ) { os << v[i] << endl; } return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const set<T>& v) { vector<T> tmp(v.begin(), v.end()); os << tmp; return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const deque<T>& v) { vector<T> tmp(v.begin(), v.end()); os << tmp; return os; }
#define MOD 1000000007LL
#define INF (1LL<<60)
/*
*/
struct Edge {
ll from, to, score;
};
int main() {
ios::sync_with_stdio(false);
ll N,M;
while(cin>>N>>M) {
vector<vector<Edge>> g(N);
REP(i, M) {
Edge e;
cin>>e.from>>e.to>>e.score;
e.from--;
e.to--;
g[e.from].PB(e);
}
VI score(N, -INF);
score[0] = 0;
bool inf = false;
ll prevScore = 0;
REP(loop, N) {
REP(i, N) {
for(auto& e : g[i]) {
ll ns = score[e.from] + e.score;
score[e.to] = max(score[e.to], ns);
}
}
if(loop==N-1 && prevScore<score[N-1]) inf=true;
prevScore = score[N-1];
}
if(inf) cout<<"inf"<<endl;
else cout<<score[N-1]<<endl;
}
return 0;
}
Submission Info
Submission Time |
|
Task |
D - Score Attack |
User |
kojingharang |
Language |
C++14 (GCC 5.4.1) |
Score |
400 |
Code Size |
3317 Byte |
Status |
AC |
Exec Time |
7 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 |
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 |
4 ms |
384 KB |
subtask_1_13.txt |
AC |
2 ms |
256 KB |
subtask_1_14.txt |
AC |
4 ms |
384 KB |
subtask_1_15.txt |
AC |
7 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 |
3 ms |
384 KB |
subtask_1_19.txt |
AC |
5 ms |
384 KB |
subtask_1_2.txt |
AC |
5 ms |
384 KB |
subtask_1_20.txt |
AC |
3 ms |
256 KB |
subtask_1_21.txt |
AC |
4 ms |
384 KB |
subtask_1_22.txt |
AC |
7 ms |
384 KB |
subtask_1_23.txt |
AC |
1 ms |
256 KB |
subtask_1_24.txt |
AC |
4 ms |
384 KB |
subtask_1_25.txt |
AC |
2 ms |
256 KB |
subtask_1_26.txt |
AC |
4 ms |
384 KB |
subtask_1_27.txt |
AC |
4 ms |
384 KB |
subtask_1_3.txt |
AC |
3 ms |
256 KB |
subtask_1_4.txt |
AC |
5 ms |
384 KB |
subtask_1_5.txt |
AC |
2 ms |
256 KB |
subtask_1_6.txt |
AC |
5 ms |
384 KB |
subtask_1_7.txt |
AC |
4 ms |
384 KB |
subtask_1_8.txt |
AC |
5 ms |
384 KB |
subtask_1_9.txt |
AC |
1 ms |
256 KB |