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
AC × 3
AC × 30
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