結果
問題 | No.2640 traO Stamps |
ユーザー |
![]() |
提出日時 | 2024-02-19 22:52:44 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 64 ms / 2,000 ms |
コード長 | 2,234 bytes |
コンパイル時間 | 2,837 ms |
コンパイル使用メモリ | 254,736 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-09-29 02:40:29 |
合計ジャッジ時間 | 6,707 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 33 |
ソースコード
#include <bits/stdc++.h>#include <vector>namespace nono {template <class T>class FenwickTree {public:FenwickTree(int size = 0): size_(size), data_(size_ + 1) {}void add(int i, const T& v) {for (++i; i <= size_; i += i & -i) {data_[i] += v;}}T sum(int i) const {T result{};for (; i > 0; i -= i & -i) {result += data_[i];}return result;}T sum(int l, int r) const {return sum(r) - sum(l);}private:int size_;std::vector<T> data_;};} // namespace nonovoid solve() {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];for (int i = 0; i <= k; i++) s[i]--;constexpr long long INF = 1e18;std::vector dist(n, std::vector<long long>(n, INF));for (int i = 0; i < m; i++) {int u, v, w;std::cin >> u >> v >> w;u--;v--;dist[u][v] = w;dist[v][u] = w;}for (int i = 0; i < n; i++) dist[i][i] = 0;for (int k = 0; k < n; k++) {for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j]);}}}nono::FenwickTree<long long> fenwick(k);for (int i = 0; i < k; i++) {fenwick.add(i, dist[s[i]][s[i + 1]]);}int q;std::cin >> q;while (q--) {int t, x, y;std::cin >> t >> x >> y;if (t == 1) {y--;if (x != 0) {long long cur = dist[s[x - 1]][s[x]];long long next = dist[s[x - 1]][y];fenwick.add(x - 1, next - cur);}if (x != k) {long long cur = dist[s[x]][s[x + 1]];long long next = dist[y][s[x + 1]];fenwick.add(x, next - cur);}s[x] = y;} else {std::cout << fenwick.sum(x, y) << '\n';}}}int main() {std::cin.tie(0)->sync_with_stdio(0);std::cout << std::fixed << std::setprecision(16);int t = 1;while (t--) solve();}