結果
問題 | No.2640 traO Stamps |
ユーザー |
|
提出日時 | 2024-02-11 17:30:02 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 285 ms / 2,000 ms |
コード長 | 1,273 bytes |
コンパイル時間 | 3,874 ms |
コンパイル使用メモリ | 255,252 KB |
最終ジャッジ日時 | 2025-02-19 05:12:50 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 33 |
ソースコード
#include <bits/extc++.h>#include <atcoder/segtree>using ll = long long int;void chmin(ll &a, ll b) {if (a > b) a = b;}ll op(ll a, ll b) { return a + b; }ll e() { return 0; }using segtree = atcoder::segtree<ll, op, e>;int main() {int N, M, K;std::cin >> N >> M >> K;std::vector<int> S(K + 1);for (int i = 0; i <= K; i++) {std::cin >> S[i];S[i]--;}std::vector dist(N, std::vector<ll>(N, 1e14));for (int i = 0; i < N; i++) {dist[i][i] = 0;}for (int i = 0; i < M; i++) {int u, v;ll w;std::cin >> u >> v >> w;u--;v--;dist[u][v] = w;dist[v][u] = w;}for (int k = 0; k < N; k++) {for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {chmin(dist[i][j], dist[i][k] + dist[k][j]);}}}segtree seg(K);for (int i = 0; i < K; i++) {seg.set(i, dist[S[i]][S[i + 1]]);}int Q;std::cin >> Q;for (int i = 0; i < Q; i++) {int T, X, Y;std::cin >> T >> X >> Y;if (T == 1) {Y--;S[X] = Y;if (X > 0) {seg.set(X - 1, dist[S[X - 1]][Y]);}if (X < K) {seg.set(X, dist[Y][S[X + 1]]);}} else {std::cout << seg.prod(X, Y) << std::endl;}}}