Submission #67963958

---

Source Code Expand

#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
namespace mlp = boost::multiprecision;
using bint = mlp::cpp_int;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using mint = modint998244353;
#define rep(i,n) for (int i=0;i<(int)(n);i++)
#define rep1(i,n) for (int i=1;i<(int)(n);i++)
#define rrep(i,n) for (ll i=n-1;i>=0;i--)
#define rrep1(i,n) for (ll i=n-1;i>0;i--)
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(a,b)
#define pi 3.141592653589793238L

//対オーバーフロー兵器
#define int long long

signed main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

  int N,M; cin>>N>>M;
  vector<vector<ll> > A(N,vector<ll>(N,2e+18));
  rep(i,N) A[i][i]=0;
  ll ans=0;

  rep(i,M){
    int a,b,c; cin>>a>>b>>c; a--; b--;
    A[a][b]=c; A[b][a]=c;
  }


  ll K,T; cin>>K>>T;
  vector<int> D(K);
  rep(i,K) cin>>D[i];
  rep(i,K) D[i]--;

  for (int i=0;i<K;i++){
    for (int j=i+1;j<K;j++){
      if (T<A[D[i]][D[j]]){
        chmin(A[D[i]][D[j]],T);
        chmin(A[D[j]][D[i]],T);
      }
    }
  }

  rep(k,N)rep(i,N)rep(j,N){
    if (A[i][j]>A[i][k]+A[k][j]){
      if (A[i][j]<1e+18) ans-=(ll)2*A[i][j];
      A[i][j]=A[i][k]+A[k][j];
    }
  }

  ll prev=-1;
  bool update=true;

  int Q; cin>>Q;
  rep(w,Q){
    int q; cin>>q;
    if (q==1){
      int x,y,t; cin>>x>>y>>t; x--; y--;
      if (A[x][y]>t) update=true;
      chmin(A[x][y],t);
      chmin(A[y][x],t);
    }

    if (q==2){
      int x; cin>>x; x--;
      rep(i,K){
        if (A[x][D[i]]>T) update=true;
        chmin(A[x][D[i]],T);
        chmin(A[D[i]][x],T);
      }
      K++; D.push_back(x);
    }
    if (q==3){
      if (!update){cout<<prev<<endl; continue;}
      update=false;
      ll ans=0;
      rep(k,N)rep(i,N)rep(j,N){
        chmin(A[i][j],A[i][k]+A[k][j]);
      }
      rep(i,N)rep(j,N) if(A[i][j]<1e+18) ans+=A[i][j];
      cout<<ans<<endl;
      prev=ans;
    }
  }



  

  return 0;
}

Submission Info

Judge Result