Submission #1384474
Source Code Expand
/*
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<memory>
#include<functional>
#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)
#define pb push_back
#define N_MAX 1000
#define INF (1LL << 50)
using namespace std;
typedef long long ll;
struct EDGE{
int to;
ll cost;
EDGE(int t, ll c){
to = t;
cost = c;
}
};
typedef vector<vector<EDGE> > AdjList;
AdjList v;
int n, m;
ll d[N_MAX+1];
bool bellman_ford(int n){
rep(i, N_MAX+1){
d[i] = INF;
}
d[0] = 0;
rep(i, n-1){
rep(j, n){
rep(k, v[j].size()){
EDGE e = v[j][k];
if(d[j] != INF && (d[e.to] > d[j] + e.cost)){
d[e.to] = d[j] + e.cost;
}
}
}
}
ll ans = d[n-1];
bool neg[N_MAX+1];
rep(i, n) neg[i] = false;
rep(i, n){
rep(j, n){
rep(k, v[j].size()){
EDGE e = v[j][k];
if(d[j] != INF && d[e.to] > d[j] + e.cost){
d[e.to] = d[j] + e.cost;
neg[e.to] = true;
}
if(neg[j] == true){
neg[e.to] = true;
}
}
}
}
return neg[n-1];
}
signed main(){
int from, to;
ll cost;
cin >> n >> m;
v = AdjList(n);
rep(i, m){
cin >> from >> to >> cost;
v[from-1].pb(EDGE(to-1, -cost));
}
if(bellman_ford(n) || d[n-1] == INF){
cout << "inf" << endl;
}else{
cout << -d[n-1] << endl;
}
}
*/
#include <iostream>
#include <vector>
using namespace std;
#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)
#define pb push_back
#define N_MAX 1000
#define INF (1LL << 51)
typedef long long ll;
struct Edge{
int from, to;
ll cost;
Edge(int f, int t, ll c) : from(f), to(t), cost(c) {}
};
int n, m;
vector<Edge> edges;
ll d[N_MAX+1];
bool bellman_ford(){
rep(i, N_MAX+1) d[i] =-INF;
d[0] = 0;
rep(i, 2*n){
for(auto &edge:edges){
if(d[edge.from] != INF && d[edge.to] < d[edge.from] + edge.cost){
d[edge.to] = d[edge.from] + edge.cost;
if(i > n) return true;
}
}
}
return false;
}
signed main(){
int f, t;
ll c;
cin >> n >> m;
rep(i, m){
cin >> f >> t >> c;
f--; t--;
edges.emplace_back(f, t, c);
}
if(bellman_ford()){
cout << "inf" << endl;
}else{
cout << d[n-1] << endl;
}
}
Submission Info
Submission Time |
|
Task |
D - Score Attack |
User |
bath_poo_ |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2674 Byte |
Status |
WA |
Exec Time |
7 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 |
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 |
256 KB |
subtask_1_13.txt |
AC |
1 ms |
256 KB |
subtask_1_14.txt |
AC |
4 ms |
256 KB |
subtask_1_15.txt |
AC |
7 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 |
4 ms |
256 KB |
subtask_1_19.txt |
AC |
5 ms |
256 KB |
subtask_1_2.txt |
AC |
4 ms |
256 KB |
subtask_1_20.txt |
AC |
1 ms |
256 KB |
subtask_1_21.txt |
AC |
4 ms |
256 KB |
subtask_1_22.txt |
AC |
7 ms |
256 KB |
subtask_1_23.txt |
WA |
1 ms |
256 KB |
subtask_1_24.txt |
AC |
5 ms |
256 KB |
subtask_1_25.txt |
WA |
2 ms |
256 KB |
subtask_1_26.txt |
AC |
4 ms |
256 KB |
subtask_1_27.txt |
WA |
4 ms |
256 KB |
subtask_1_3.txt |
AC |
3 ms |
256 KB |
subtask_1_4.txt |
AC |
4 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 |
4 ms |
256 KB |
subtask_1_8.txt |
AC |
4 ms |
256 KB |
subtask_1_9.txt |
AC |
1 ms |
256 KB |