Submission #1590784
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, double d); bool Search(int startPoint,double infVal); double Distance(int targetPoint){return DistanceFormStart[targetPoint];} protected: int PointNum=0; vector< multimap<int,double> > Connect; // 相手の点番号と距離 vector<int> BeforePoint; vector<double> 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, double d){ Connect[a].emplace(b,d); } bool class_BellmanFord::Search(int startPoint, double infVal){ for(int i=0;i<PointNum;i++){ DistanceFormStart[i] = infVal; BeforePoint[i] = -1; } DistanceFormStart[startPoint] = 0.0; for(int i=0;i<=PointNum;i++){ bool flagLast = (i==PointNum); bool flagUpdate = false; 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]){ if (flagLast){ return false; } flagUpdate = true; DistanceFormStart[c.first] = newScore; BeforePoint[c.first] = u; } } } if (flagUpdate==false){break;} } 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,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 | D - Score Attack |
User | t_tkd3a |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1979 Byte |
Status | WA |
Exec Time | 22 ms |
Memory | 384 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 | 1 ms | 256 KB |
subtask_1_10.txt | AC | 1 ms | 256 KB |
subtask_1_11.txt | AC | 3 ms | 256 KB |
subtask_1_12.txt | AC | 12 ms | 384 KB |
subtask_1_13.txt | AC | 1 ms | 256 KB |
subtask_1_14.txt | AC | 10 ms | 384 KB |
subtask_1_15.txt | AC | 22 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 | 2 ms | 384 KB |
subtask_1_19.txt | AC | 3 ms | 384 KB |
subtask_1_2.txt | AC | 2 ms | 384 KB |
subtask_1_20.txt | AC | 1 ms | 256 KB |
subtask_1_21.txt | AC | 2 ms | 384 KB |
subtask_1_22.txt | AC | 3 ms | 384 KB |
subtask_1_23.txt | WA | 1 ms | 256 KB |
subtask_1_24.txt | AC | 3 ms | 384 KB |
subtask_1_25.txt | WA | 4 ms | 256 KB |
subtask_1_26.txt | AC | 5 ms | 384 KB |
subtask_1_27.txt | WA | 8 ms | 384 KB |
subtask_1_3.txt | AC | 2 ms | 384 KB |
subtask_1_4.txt | AC | 2 ms | 384 KB |
subtask_1_5.txt | AC | 4 ms | 256 KB |
subtask_1_6.txt | AC | 8 ms | 384 KB |
subtask_1_7.txt | AC | 2 ms | 384 KB |
subtask_1_8.txt | AC | 2 ms | 384 KB |
subtask_1_9.txt | AC | 1 ms | 256 KB |