Submission #4023857


Source Code Expand

#include<bits/stdc++.h>
using namespace std;
using Int = long long;
//BEGIN CUT HERE
template <typename T>
vector<T> dijkstra(int s,vector<vector<pair<int, T> > > & G){  
  const T INF = numeric_limits<T>::max();    
  using P = pair<T, int>;
  int n=G.size();
  vector<T> d(n,INF);
  vector<int> b(n,-1);
  priority_queue<P,vector<P>,greater<P> > q;
  d[s]=0;
  q.emplace(d[s],s);
  while(!q.empty()){
    P p=q.top();q.pop();
    int v=p.second;
    if(d[v]<p.first) continue;
    for(auto& e:G[v]){
      int u=e.first;
      T c=e.second;
      if(d[u]>d[v]+c){
        d[u]=d[v]+c;
        b[u]=v;
        q.emplace(d[u],u);
      }
    }
  }
  return d;
}
//END CUT HERE

signed main(){
  int n,l;
  cin>>n>>l;
  using P = pair<int, Int>;
  vector<vector<P> > G(l+1);
  for(int i=0;i<n;i++){
    int a,b,c;
    cin>>a>>b>>c;
    G[a].emplace_back(b,c);
  }
  for(int i=0;i<l;i++)
    G[i+1].emplace_back(i,0);
  cout<<dijkstra(0,G)[l]<<endl;
  return 0;
}

/*
  verified on 2017/11/27
  http://arc026.contest.atcoder.jp/tasks/arc026_3
*/

Submission Info

Submission Time
Task C - 蛍光灯
User beet
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1096 Byte
Status AC
Exec Time 132 ms
Memory 9980 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 60 / 60 40 / 40
Status
AC × 4
AC × 33
AC × 48
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
Subtask1 sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt
Subtask2 sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.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
sample_04.txt AC 1 ms 256 KB
subtask1_01.txt AC 3 ms 384 KB
subtask1_02.txt AC 4 ms 384 KB
subtask1_03.txt AC 3 ms 384 KB
subtask1_04.txt AC 4 ms 384 KB
subtask1_05.txt AC 4 ms 512 KB
subtask1_06.txt AC 3 ms 512 KB
subtask1_07.txt AC 4 ms 512 KB
subtask1_08.txt AC 4 ms 384 KB
subtask1_09.txt AC 3 ms 384 KB
subtask1_10.txt AC 3 ms 256 KB
subtask1_11.txt AC 4 ms 512 KB
subtask1_12.txt AC 4 ms 384 KB
subtask1_13.txt AC 3 ms 512 KB
subtask1_14.txt AC 3 ms 384 KB
subtask1_15.txt AC 2 ms 384 KB
subtask1_16.txt AC 4 ms 512 KB
subtask1_17.txt AC 2 ms 384 KB
subtask1_18.txt AC 3 ms 384 KB
subtask1_19.txt AC 2 ms 384 KB
subtask1_20.txt AC 4 ms 512 KB
subtask1_21.txt AC 4 ms 512 KB
subtask1_22.txt AC 4 ms 512 KB
subtask1_23.txt AC 4 ms 512 KB
subtask1_24.txt AC 4 ms 512 KB
subtask1_25.txt AC 4 ms 512 KB
subtask1_26.txt AC 4 ms 512 KB
subtask1_27.txt AC 4 ms 512 KB
subtask1_28.txt AC 4 ms 512 KB
subtask1_29.txt AC 5 ms 512 KB
subtask2_01.txt AC 43 ms 3964 KB
subtask2_02.txt AC 107 ms 7040 KB
subtask2_03.txt AC 53 ms 2176 KB
subtask2_04.txt AC 127 ms 9084 KB
subtask2_05.txt AC 91 ms 6652 KB
subtask2_06.txt AC 36 ms 6016 KB
subtask2_07.txt AC 14 ms 768 KB
subtask2_08.txt AC 53 ms 6016 KB
subtask2_09.txt AC 106 ms 5760 KB
subtask2_10.txt AC 126 ms 9980 KB
subtask2_11.txt AC 126 ms 9472 KB
subtask2_12.txt AC 121 ms 9472 KB
subtask2_13.txt AC 124 ms 9980 KB
subtask2_14.txt AC 132 ms 9980 KB
subtask2_15.txt AC 102 ms 8448 KB