战争 I（最短路+离线算法）

题目描述
某年，白国和委国之间的战争爆发了！

然而，在委国指挥官委兆的眼里，白国人不堪一击。现在他手上有一张白国的地图，发现白国有 n 个据点，m 条无向道路，他们有各自的长度。于是他决定按一定顺序破坏白国的一些据点，使得所有连接这些据点与其他据点的道路无法通行。同时，为了更有效率的攻城略地，也为了满足委兆的成就感，他有时还想知道当前某两个据点间的最短路径长。请编程满足他的要求。

输入
第一行两个正整数 n,m。

接下来 m 行，每行有三个数 a,b,v表示一条连接 a,b的无向边。

接下来一行一个正整数 q 。

接下来 q 行，每行是两个数 “ 1 a ” 或是三个数 “ 2 a b ” ,含义如题面所述。

输出
对于每个“ 2 a b ” 操作，输出对应的结果。
若两点不连通，输出−1 。

样例输入
4 4
1 2 6
3 4 1
1 3 4
1 4 9
3
2 1 4
1 3
2 1 4

样例输出
5
9

提示
对于 100%的数据 n≤200,m≤n∗(n−1)/2,q≤2×10⁴,v≤1000保证所有的操作合法。

思路
将所有问题离线运算，在记录问题时，先锁定被标记的点，对每个问题，从最后计算到最前，并倒序解锁标记点，每次解锁对全图进行更新

代码实现

#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=205;
const int M=50005;
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const ull sed=31;
const ll mod=10000019;
const double eps=1e-5;
const double PI=acos(-1.0);
typedef pair<int,int>P;
typedef pair<double,double>Pd;
          
template<class T>void read(T &x)
{
    x=0;int f=0;char ch=getchar();
    while(ch<'0'||ch>'9') {f|=(ch=='-');ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    x=f?-x:x;
    return;
}
  
ll mp[N][N];
int n,m,q;
P qus[M];
bool vis[N];
vector<ll>ans;
  
int main()
{
      
    //freopen("a.txt","r",stdin);
    read(n);read(m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)  
            if(i!=j) mp[i][j]=LINF;
    for(int i=0;i<m;i++)
    {
        int u,v;ll w;
        read(u);read(v);read(w);
        mp[u][v]=min(mp[u][v],w);
        mp[v][u]=mp[u][v];
    }
    read(q);
    for(int i=1;i<=q;i++)
    {
        int op,a,b;
        qus[i]=P(0,0);
        read(op);
        if(op==1) 
        {
            read(a);
            if(!vis[a]) qus[i]=P(a,0);
            vis[a]=true;
        }
        else
        {
            read(a);read(b);
            qus[i]=P(a,b);
        }
    }
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(!vis[i] && !vis[j] && !vis[k]) 
                    mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]);
    for(int len=q;len;len--)
    {
        if(!qus[len].first && !qus[len].second) continue;
        if(qus[len].second)
        {
            int u=qus[len].first,v=qus[len].second;
            if(vis[u] || vis[v]) ans.push_back(LINF);
            else ans.push_back(mp[u][v]);
        }
        else
        {
            int u=qus[len].first;
            vis[u]=false;
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    if(!vis[i] && !vis[j]) 
                    {
                        mp[i][u]=min(mp[i][u],mp[i][j]+mp[j][u]);
                        mp[u][i]=min(mp[u][i],mp[u][j]+mp[j][i]);
                    }
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    if(!vis[i] && !vis[j])
                        mp[i][j]=min(mp[i][j],mp[i][u]+mp[u][j]); 
        }
    }
    for(int i=ans.size()-1;i>=0;i--)
    {
        if(ans[i]==LINF) puts("-1");
        else printf("%lld\n",ans[i]);
    }
    return 0;
}