結果
問題 | No.614 壊れたキャンパス |
ユーザー |
![]() |
提出日時 | 2017-12-14 00:56:30 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 260 ms / 2,000 ms |
コード長 | 1,152 bytes |
コンパイル時間 | 1,573 ms |
コンパイル使用メモリ | 165,592 KB |
実行使用メモリ | 14,248 KB |
最終ジャッジ日時 | 2024-12-14 10:38:53 |
合計ジャッジ時間 | 5,256 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
コンパイルメッセージ
main.cpp:19:1: warning: ISO C++ forbids declaration of ‘main’ with no type [-Wreturn-type] 19 | main(){ | ^~~~
ソースコード
#include <bits/stdc++.h>using namespace std;struct C {int b,c;long long v;};int n,m,k,s,t;vector<C> css[200010];bool byb(C const&c1,C const&c2){return c1.b<c2.b;}bool byc(C const&c1,C const&c2){return c1.c<c2.c;}main(){cin>>n>>m>>k>>s>>t;for(int i=0;i<m;++i){int a;C c;cin>>a>>c.b>>c.c;css[a].push_back(c);}{C c;c.b=t;c.c=s;c.v=0;css[0].push_back(c);css[n].push_back(c);}for(int i=0;i<n;++i){if(css[i+1].empty()){cout<<-1;exit(0);}sort(css[i].begin(),css[i].end(),byc);int cc=css[i].size();for(int j=1;j<cc;++j){C&c0=css[i][j-1];C&c1=css[i][j];if(c1.v>c0.v+(c1.c-c0.c)){c1.v=c0.v+(c1.c-c0.c);}}for(int j=cc-2;j>=0;--j){C&c1=css[i][j];C&c0=css[i][j+1];if(c1.v>c0.v+(c0.c-c1.c)){c1.v=c0.v+(c0.c-c1.c);}}sort(css[i+1].begin(),css[i+1].end(),byb);int l=0;for(auto& d:css[i+1]){while(l<cc&&css[i][l].c<d.b){++l;}long long v1= l==0 ? 1ll<<62 : css[i][l-1].v+(d.b-css[i][l-1].c);long long v2= l==cc ? 1ll<<62 : css[i][l].v+(css[i][l].c-d.b);d.v=min(v1,v2);}}cout<<css[n][0].v;}