結果
問題 | No.2640 traO Stamps |
ユーザー |
|
提出日時 | 2024-02-19 22:00:14 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 70 ms / 2,000 ms |
コード長 | 1,401 bytes |
コンパイル時間 | 1,920 ms |
コンパイル使用メモリ | 199,612 KB |
最終ジャッジ日時 | 2025-02-19 16:59:06 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 33 |
ソースコード
#include<bits/stdc++.h>using namespace std;using ll=long long;namespace Lib {struct BIT {vector<ll> a;int sz;BIT(int n) : sz(n), a(n + 1) {}void add(int p, ll v) {for (p += 1; p <= sz; p += p & -p) a[p] += v;}ll sum(int l, int r) {ll ret = 0;for (; r > 0; r -= r & -r) ret += a[r];for (; l > 0; l -= l & -l) ret -= a[l];return ret;}};} // namespace Libint main(){ios::sync_with_stdio(false);cin.tie(nullptr);int N,M,K;cin>>N>>M>>K;vector S(K+1,0);for(int &i:S)cin>>i,--i;vector dist(N,vector(N,(ll)1e18));for(int i=0;i<M;i++){int A,B,C;cin>>A>>B>>C;--A,--B;dist[A][B]=C;dist[B][A]=C;}for(int i=0;i<N;i++)dist[i][i]=0;for(int i=0;i<N;i++){for(int j=0;j<N;j++){for(int k=0;k<N;k++){dist[j][k]=min(dist[j][k],dist[j][i]+dist[i][k]);}}}// for(int i=0;i<N;i++){// for(int j=0;j<N;j++)cout<<dist[i][j]<<' ';cout<<'\n';// }Lib::BIT seg(K);for(int i=0;i<K;i++){seg.add(i,dist[S[i]][S[i+1]]);}int Q;cin>>Q;while(Q--){int T,X,Y;cin>>T>>X>>Y;if(T==1){--Y;if(X>0)seg.add(X-1,-dist[S[X-1]][S[X]]);if(X<K)seg.add(X,-dist[S[X]][S[X+1]]);S[X]=Y;if(X>0)seg.add(X-1,dist[S[X-1]][S[X]]);if(X<K)seg.add(X,dist[S[X]][S[X+1]]);}else{cout<<seg.sum(X,Y)<<'\n';}}}