Submission #1590925
Source Code Expand
#include<bits/stdc++.h> using namespace std; using ll = int64_t; class class_BellmanFord{ public: class_BellmanFord(){}; virtual ~class_BellmanFord(){}; void Init(int N); void Set_1Way(int a,int b, ll d); bool Search(int startPoint, int endPoint, ll infVal); double Distance(int targetPoint){return DistanceFormStart[targetPoint];} protected: int PointNum=0; vector< multimap<int,ll> > Connect; // 相手の点番号と距離 vector<int> BeforePoint; vector<ll> DistanceFormStart; }; void class_BellmanFord::Init(int N){ Connect.clear(); Connect.resize(N); DistanceFormStart.clear(); DistanceFormStart.resize(N); BeforePoint.clear(); BeforePoint.resize(N); PointNum = N; } void class_BellmanFord::Set_1Way(int a, int b, ll d){ Connect[a].emplace(b,d); } bool class_BellmanFord::Search(int startPoint, int endPoint, ll infVal){ for(int i=0;i<PointNum;i++){ DistanceFormStart[i] = infVal; BeforePoint[i] = -1; } DistanceFormStart[startPoint] = 0; for(int i=0;i<PointNum-1;i++){ for(int u=0;u<PointNum;u++){ if (DistanceFormStart[u]==infVal){continue;} for(auto c : Connect[u]){ double newScore = DistanceFormStart[u] + c.second; if (newScore < DistanceFormStart[c.first]){ DistanceFormStart[c.first] = newScore; BeforePoint[c.first] = u; } } } } vector<char> nega(PointNum); for(int i=0;i<PointNum;i++){ for(int u=0;u<PointNum;u++){ if (DistanceFormStart[u]==infVal){continue;} for(auto c : Connect[u]){ double newScore = DistanceFormStart[u] + c.second; if (newScore < DistanceFormStart[c.first]){ DistanceFormStart[c.first] = newScore; nega[c.first]=1; } if (nega[u]==1){ nega[c.first]=1; } } } } // endPoint に届かない所の負ループは無視! if (nega[endPoint]==1){return false;} return true; } int main(int , char **) { int N,M; cin >> N >> M; class_BellmanFord graph; graph.Init(N); for(int i=0;i<M;i++){ int a,b,c; cin >> a >> b >> c; a--;b--; // 入力は1始点、これを 0 始点とする graph.Set_1Way(a,b,-c); } if (graph.Search(0,N-1,LLONG_MAX) == false){printf("inf\n");return 0;} double ans = graph.Distance(N-1); printf("%ld\n", (ll)(ans * -1.0) ); return 0; }
Submission Info
Submission Time | |
---|---|
Task | A - Between Two Integers |
User | t_tkd3a |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2340 Byte |
Status | RE |
Exec Time | 297 ms |
Memory | 384 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 100 | ||||||
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_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | RE | 297 ms | 256 KB |
sample_02.txt | RE | 95 ms | 256 KB |
sample_03.txt | RE | 95 ms | 256 KB |
subtask_1_1.txt | RE | 95 ms | 256 KB |
subtask_1_2.txt | WA | 1 ms | 256 KB |
subtask_1_3.txt | RE | 97 ms | 384 KB |
subtask_1_4.txt | RE | 95 ms | 256 KB |
subtask_1_5.txt | RE | 96 ms | 256 KB |
subtask_1_6.txt | RE | 95 ms | 256 KB |
subtask_1_7.txt | RE | 95 ms | 256 KB |