結果
問題 | No.2640 traO Stamps |
ユーザー |
![]() |
提出日時 | 2024-02-19 21:59:24 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 77 ms / 2,000 ms |
コード長 | 1,551 bytes |
コンパイル時間 | 2,968 ms |
コンパイル使用メモリ | 250,200 KB |
実行使用メモリ | 9,984 KB |
最終ジャッジ日時 | 2024-09-29 01:57:44 |
合計ジャッジ時間 | 7,109 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 33 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/segtree>using namespace std;using ll = long long;ll inf = 1e18;ll op(ll a, ll b) { return a + b; }ll e() { return 0; }using segtree = atcoder::segtree<ll, op, e>;int N, M, K, Q;int S[200010];ll dist[210][210];template<typename A, int N, typename T>void Fill(A (&arr)[N], const T &val){fill((T*)arr, (T*)(arr + N), val);}int main(void){ios::sync_with_stdio(false);cin.tie(nullptr);cin >> N >> M >> K;Fill(dist, inf);for(int i = 0;i <= K;i++){cin >> S[i]; S[i]--;}for(int i = 0;i < N;i++)dist[i][i] = 0;for(int i = 0;i < M;i++){int a, b; ll c; cin >> a >> b >> c;a--, b--;dist[a][b] = min(dist[a][b], c);dist[b][a] = min(dist[b][a], c);}for(int k = 0;k < N;k++){for(int i = 0;i < N;i++){for(int j = 0;j < N;j++){dist[i][j] = min(dist[i][k] + dist[k][j], dist[i][j]);}}}segtree seg(K);for(int i = 0;i < K;i++){seg.set(i, dist[S[i]][S[i + 1]]);}cin >> Q;while(Q--){int t; cin >> t;if(t == 1){int x, y; cin >> x >> y;y--;S[x] = y;if(x > 0){seg.set(x - 1, dist[S[x - 1]][S[x]]);}if(x < K){seg.set(x, dist[S[x]][S[x + 1]]);}}else{int x, y; cin >> x >> y;cout << seg.prod(x, y) << "\n";}}return 0;}