結果
問題 | No.2640 traO Stamps |
ユーザー |
|
提出日時 | 2024-02-13 17:06:45 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 179 ms / 2,000 ms |
コード長 | 1,350 bytes |
コンパイル時間 | 4,239 ms |
コンパイル使用メモリ | 254,220 KB |
最終ジャッジ日時 | 2025-02-19 05:58:48 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 33 |
ソースコード
#include<bits/stdc++.h>#include<atcoder/all>using namespace std;using namespace atcoder;using ll = long long;int main(){cin.tie(0);ios::sync_with_stdio(0);int n, m, k;cin >> n >> m >> k;vector<int> s(k+1);for(int i = 0; i < k + 1; i++) {cin >> s[i];s[i]--;}vector<vector<ll>> wf(n, vector<ll>(n, LONG_MAX >> 1));for(int i = 0; i < n; i++) wf[i][i] = 0;for(int i = 0; i < m; i++){int a, b, c;cin >> a >> b >> c;a--,b--;wf[a][b] = c;wf[b][a] = c;}for(int l = 0; l < n; l++){for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){wf[i][j] = min(wf[i][j], wf[i][l] + wf[l][j]);}}}fenwick_tree<ll> tree(k);for(int i = 0; i < k; i++){tree.add(i, wf[s[i]][s[i+1]]);}int q;cin >> q;while(q--){int t;cin >> t;if(t == 1){int x, y;cin >> x >> y;y--;if(x != 0) tree.add(x-1, wf[s[x-1]][y] - wf[s[x-1]][s[x]]);if(x != k) tree.add(x, wf[y][s[x+1]] - wf[s[x]][s[x+1]]);s[x] = y;}if(t == 2){int x,y;cin >> x >> y;cout << tree.sum(x, y) << endl;}}}