結果
問題 | No.2640 traO Stamps |
ユーザー |
![]() |
提出日時 | 2024-02-19 22:09:01 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 294 ms / 2,000 ms |
コード長 | 1,386 bytes |
コンパイル時間 | 2,255 ms |
コンパイル使用メモリ | 202,468 KB |
最終ジャッジ日時 | 2025-02-19 17:03:37 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 33 |
ソースコード
#include <bits/stdc++.h>using namespace std;#include <atcoder/segtree>using namespace atcoder;long long op(long long x, long long y) {return x+y;}long long e() {return 0LL;}int main() {int N, M, K;cin >> N >> M >> K;vector<int> S(K+1);for( int i = 0; i <= K; i++ ) {cin >> S[i];S[i]--;}constexpr long long INF = 1LL<<60;vector dist(N, vector<long long>(N, INF));for( int i = 0; i < N; i++ ) {dist[i][i] = 0;}for( int i = 0; i < M; i++ ) {int a, b;long long c;cin >> a >> b >> c;a--, b--;dist[a][b] = 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][j], dist[i][k]+dist[k][j]);}}}segtree<long long, op, e> seg(K);for( int i = 0; i < K; i++ ) {seg.set(i, dist[S[i]][S[i+1]]);}int Q;cin >> Q;for( int i = 0; i < Q; i++ ) {int t, x, y;cin >> t >> x >> y;if( t == 1 ) {y--;S[x] = y;if( x-1 >= 0 ) seg.set(x-1, dist[S[x-1]][S[x]]);if( x+1 <= K ) seg.set(x, dist[S[x]][S[x+1]]);}if( t == 2 ) {cout << seg.prod(x, y) << endl;}}}