Submission #1286674
Source Code Expand
// #includes {{{
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define RREP(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define FOR(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();++i)
#define LET(x,a) __typeof(a) x(a)
//#define IFOR(i,it,c) for(__typeof((c).begin())it=(c).begin();it!=(c).end();++it,++i)
#define ALL(c) (c).begin(), (c).end()
#define MP make_pair
#define EXIST(e,s) ((s).find(e)!=(s).end())
#define RESET(a) memset((a),0,sizeof(a))
#define SET(a) memset((a),-1,sizeof(a))
#define PB push_back
#define DEC(it,command) __typeof(command) it=command
//debug
#define dump(x) cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define debug2(x) cerr << #x << " = [";REP(__ind,(x).size()){cerr << (x)[__ind] << ", ";}cerr << "] (L" << __LINE__ << ")" << endl;
typedef long long Int;
//const Int INF=10000000000000ll;
//const Int INF=1e+15;
const Int INF=1ll<<49;
typedef unsigned long long uInt;
typedef long double rn;
typedef pair<int,int> pii;
/*
#ifdef MYDEBUG
#include"debug.h"
#include"print.h"
#endif
*/
// }}}
//{{{ Graph
typedef Int Weight;
struct Edge {
int src, dst, rev;
Weight weight;
Edge(int src, int dst, Weight weight=1,int rev=-1) :
src(src), dst(dst), weight(weight), rev(rev) { }
};
bool operator < (const Edge &e, const Edge &f) {
return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
//typedef vector<Edges> Graph;
struct Graph:vector<Edges>{
Graph(){}
Graph(const int &n){this->assign(n,Edges());}
//add directional edge
void addEdge(int from ,int to, Weight w=1){
this->at(from).push_back(Edge(from,to,w));
}
};
//}}}
int N,M;
Graph G;
bool shortestPath(const Graph g, int s,
vector<Weight> &dist, vector<int> &prev) {
int n = g.size();
dist.assign(n, INF+INF); dist[s] = 0;
prev.assign(n, -2);
bool valid = true;
// bool negative_cycle = false;
REP(k, n) REP(i, n) FOR(e,g[i]) {
// if(k!=n-1 and dist[e->dst] == INF+INF)continue;
if (dist[e->dst] > dist[e->src] + e->weight) {
dist[e->dst] = dist[e->src] + e->weight;
prev[e->dst] = e->src;
/*
if (k == n-1) {
dist[e->dst] = -INF;
// negative_cycle = true;
}
*/
}
}
Int distN = dist[n-1];
REP(k, n) REP(i, n) FOR(e,g[i]) {
// if(k!=n-1 and dist[e->dst] == INF+INF)continue;
if (dist[e->dst] > dist[e->src] + e->weight) {
dist[e->dst] = dist[e->src] + e->weight;
prev[e->dst] = e->src;
/*
if (k == n-1) {
dist[e->dst] = -INF;
// negative_cycle = true;
}
*/
}
}
if(dist[n-1]<distN)return false;
else return true;
// return !negative_cycle;
}
vector<int> buildPath(const vector<int> &prev, int t) {
vector<int> path;
for (int u = t; u >= 0; u = prev[u])
path.push_back(u);
reverse(path.begin(), path.end());
return path;
}
int main(){
cin>>N>>M;
G.assign(N,Edges());
REP(i,M){
Int a,b,c;
cin>>a>>b>>c;
a--;b--;
G.addEdge(a,b,-c);
}
// memset(vis,false,sizeof(vis));
vector<Weight> dist;
vector<int> prev;
bool b = shortestPath(G,0,dist,prev);
if(!b){
cout<<"inf"<<endl;
}else{
cout<<-dist[N-1]<<endl;
}
return 0;
}
Submission Info
Submission Time |
|
Task |
D - Score Attack |
User |
chaemon |
Language |
C++14 (GCC 5.4.1) |
Score |
400 |
Code Size |
3473 Byte |
Status |
AC |
Exec Time |
13 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 |
7 ms |
384 KB |
subtask_1_13.txt |
AC |
4 ms |
256 KB |
subtask_1_14.txt |
AC |
7 ms |
384 KB |
subtask_1_15.txt |
AC |
13 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 |
6 ms |
384 KB |
subtask_1_19.txt |
AC |
12 ms |
384 KB |
subtask_1_2.txt |
AC |
6 ms |
384 KB |
subtask_1_20.txt |
AC |
4 ms |
256 KB |
subtask_1_21.txt |
AC |
6 ms |
384 KB |
subtask_1_22.txt |
AC |
13 ms |
384 KB |
subtask_1_23.txt |
AC |
1 ms |
256 KB |
subtask_1_24.txt |
AC |
8 ms |
384 KB |
subtask_1_25.txt |
AC |
3 ms |
256 KB |
subtask_1_26.txt |
AC |
6 ms |
384 KB |
subtask_1_27.txt |
AC |
6 ms |
384 KB |
subtask_1_3.txt |
AC |
4 ms |
384 KB |
subtask_1_4.txt |
AC |
6 ms |
384 KB |
subtask_1_5.txt |
AC |
3 ms |
256 KB |
subtask_1_6.txt |
AC |
7 ms |
384 KB |
subtask_1_7.txt |
AC |
5 ms |
384 KB |
subtask_1_8.txt |
AC |
6 ms |
384 KB |
subtask_1_9.txt |
AC |
1 ms |
256 KB |