結果
問題 |
No.2321 Continuous Flip
|
ユーザー |
|
提出日時 | 2025-08-26 14:29:27 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 242 ms / 2,000 ms |
コード長 | 1,108 bytes |
コンパイル時間 | 1,900 ms |
コンパイル使用メモリ | 203,484 KB |
実行使用メモリ | 30,668 KB |
最終ジャッジ日時 | 2025-08-26 14:29:40 |
合計ジャッジ時間 | 12,051 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 30 |
ソースコード
#include<bits/stdc++.h> using namespace std; const int N=2e5+5; using ll=long long; const ll inf=1e18; int c,T,n,m,a[N]; ll sum,dis[N]; bool vis[N]; vector<pair<int,int>>e[N]; struct node{ int id;ll d; bool operator<(const node &b)const{return d>b.d;} }tmp; priority_queue<node>pq; int main() { ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); // freopen("card.in","r",stdin); // freopen("card.out","w",stdout); T=1; while(T--) { cin>>n>>m>>c,sum=0; for(int i=1;i<=n;i++)cin>>a[i],sum+=a[i]; for(int i=0;i<=n;i++)e[i].clear(),dis[i]=inf,vis[i]=0; for(int i=1;i<=n;i++) { e[i-1].emplace_back(i,a[i]); e[i].emplace_back(i-1,a[i]); } for(int i=1;i<=m;i++) { int l,r,w=c; cin>>l>>r; e[l-1].emplace_back(r,w); e[r].emplace_back(l-1,w); } dis[0]=0,pq.emplace((node){0,0}); while(!pq.empty()) { tmp=pq.top();pq.pop(); int x=tmp.id; if(vis[x])continue; vis[x]=1; for(auto y:e[x])if(dis[x]+y.second<dis[y.first]) { dis[y.first]=dis[x]+y.second; pq.emplace((node){y.first,dis[y.first]}); } } cout<<sum-dis[n]<<'\n'; } return 0; }