Submission #58695774

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
using ui = unsigned;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,l,r) for(int i=(l);i>=(r);--i)
#define repn(i,n)  for(int i=0;i<(n);++i)
#define sizc(x) ((int)x.size())
#define allc(x) x.begin(),x.end()
#define fir first
#define sec second
constexpr int N = 305, M = 2e5+5;
int n,m,q;
struct star{
    int u,v,w;
}e[M];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;

using ui = unsigned;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,l,r) for(int i=(l);i>=(r);--i)
#define repn(i,n)  for(int i=0;i<(n);++i)
#define sizc(x) ((int)x.size())
#define allc(x) x.begin(),x.end()
#define fir first
#define sec second

constexpr int N = 305, M = 2e5+5;

int n,m,q;
struct star{
    int u,v,w;
}e[M];
bool ban[M];
ll dis[N][N];
int op[M],x[M],y[M];
ll ans[M];

signed main(){
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>n>>m>>q;
    rep(i,1,m)cin>>e[i].u>>e[i].v>>e[i].w;
    rep(i,1,n)rep(j,1,n)dis[i][j]=1e18;
    rep(i,1,n)dis[i][i]=0;
    rep(i,1,q){
        cin>>op[i]>>x[i];
        if(op[i]==2)cin>>y[i];
        if(op[i]==1)ban[x[i]]=1;
    }
    rep(i,1,m)if(!ban[i]){
        int u=e[i].u,v=e[i].v,w=e[i].w;
        dis[u][v]=dis[v][u]=w;
    }
    rep(k,1,n)rep(i,1,n)rep(j,1,n)dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
    per(i,q,1){
        if(op[i]==1){
            int u=e[x[i]].u,v=e[x[i]].v,w=e[x[i]].w;
            rep(a,1,n)rep(b,1,n){
                dis[a][b]=min(dis[a][b],dis[a][u]+dis[v][b]+w);
                dis[a][b]=min(dis[a][b],dis[a][v]+dis[u][b]+w);
            }
        }
        else ans[i]=dis[x[i]][y[i]];
    }
    rep(i,1,q)if(op[i]==2){
        if(ans[i]<1e18)cout<<ans[i]<<'\n';
        else cout<<"-1\n";
    }
}

Submission Info

Judge Result