Submission #58723312

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>
#define TxtIO freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); freopen("error.txt","w", stderr) ;
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define oset tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
typedef long long tds;
vector<vector<tds>> floydw(int n, vector<pair<int,tds>> adj[]){
    //
    tds INF=INT64_MAX;
    //
    vector<vector<tds>> dist(n,vector<tds> (n,INF));
    for(int i=0;i<n;i++){
        dist[i][i]=0;
    }
    for(int i=0;i<n;i++){
        for(auto j: adj[i]){
            dist[i][j.first]=min(dist[i][j.first],j.second);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include<bits/stdc++.h>
#define TxtIO freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); freopen("error.txt","w", stderr) ;
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define oset tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

typedef long long tds;
vector<vector<tds>> floydw(int n, vector<pair<int,tds>> adj[]){
    //
    tds INF=INT64_MAX;
    //
    vector<vector<tds>> dist(n,vector<tds> (n,INF));
    for(int i=0;i<n;i++){
        dist[i][i]=0;
    }
    for(int i=0;i<n;i++){
        for(auto j: adj[i]){
            dist[i][j.first]=min(dist[i][j.first],j.second);
        }
    }
    for(int k=0;k<n;k++){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(dist[i][k]<INF && dist[k][j]<INF){
                    dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
                }
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(dist[i][j]==INF){
                dist[i][j]=-1;
            }
        }
    }
    return dist;
}

int main(){
    int n,m,q;
    cin>>n>>m>>q;
    vector<pair<int,pair<int,tds>>> v(m);
    vector<pair<int,tds>> adj[n]; 
    for(int i=0;i<m;i++){
        int a,b;long long c;
        cin>>a>>b>>c;
        a--;b--;
        v[i]={a,{b,c}};
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
    auto dist=floydw(n,adj);
    set<int> s;
    for(int i=0;i<q;i++){
        int t;cin>>t;
        if(t==1){
            int y;cin>>y;y--;
            s.insert(y);
            vector<pair<int,tds>> bdj[n]; 
            for(int i=0;i<m;i++){
                if(s.find(i)==s.end()){
                    int a=v[i].first;
                    int b=v[i].second.first;
                    // cout<<a<<" "<<b
                    long long c=v[i].second.second;
                    bdj[a].push_back({b,c});
                    bdj[b].push_back({a,c});
                }
            }
            dist=floydw(n,bdj);
        }
        else{
            int x,y;cin>>x>>y;x--;y--;
            cout<<dist[x][y]<<endl;
        }
    }
    return 0;
}

Submission Info

Judge Result