题目

一放假，小 L 就开心规划好自己的假期安排。
她决定去 n 个旅游景点玩。而这些旅游景点之间达成了合作，某两个景点之间会有价格固定的直通大巴（中间不会在其他景点停车）。因此，小 L 决定旅游期间直接乘坐直通大巴在各个旅游景点间往返，并且她希望每次前往另一个景点时花费最小。
由于现在处于疫情期间，每个景点都应该按照规定进行消毒。因为小 L 非常怕感染，所以她决定，只乘坐起点和目的地都进行过至少一次消毒的大巴。
输入：
第一行是 n,m,s,q。代表这 n 个景点之间有 m 条线路（即直通大巴），小 L 现在正处在编号为 s 的景点，q 为信息数量。
我们默认 s 号景点已消过毒。
接下来 m 行，每行三个数 u,v,w。代表编号为 u 的景点与编号为 v 的景点之间存在票价为 w 的单向（从 u 到 v）直通大巴。（存在重边和自环，且有可能 u=v）
接下来 q 行是信息，每行两个数 op,x。
共有两种情况：
1 x，代表编号为 x 的景点进行了一次消毒。
2 x，代表小 L 要从当前景点 y 去到编号为 x 的景点。请注意，如果小 L 不能到达 x 号景点那么她的“当前位置”不变，即仍然在 y 号景点。否则“当前位置”为 x 号景点。
输出：
对于每个 op=2 的操作，如果 x 号景点没有进行过至少一次消毒，或者小 L 无法到达 x 号景点，请输出 -1 。否则，请输出从当前景点出发到 x 号景点的最小费用。

题解

点的数量很少，300
因此op=1时通过x点去松弛一下全部点O(n^2)；op=2时判断一下输出即可O(1)
最高时间复杂度为O(n*n*n)。
不明白为什么要每次一松弛，直接最开始floyd为什么不行？？通过率为0？？

代码

#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int n, m, s, q, edge[500][500],vis[500];
void floyd(int k) {
    for(int i = 1;i <= n;i ++) 
        for(int j = 1;j <= n;j ++) 
            if(edge[i][k] < INF && edge[k][j] < INF)
                edge[i][j] = min(edge[i][k] + edge[k][j], edge[i][j]);
}
int main()
{

    cin>>n>>m>>s>>q;
    int cur = s;
    memset(edge, 0x3f, sizeof edge);
    int u, v, w;
    for(int i = 1;i <= m;i ++) {
        cin>>u>>v>>w;
        if(u != v) edge[u][v] = min(edge[u][v], w);
    }
    for(int i = 1;i <= n;i ++) edge[i][i] = 0;
    vis[s] = 1;
    floyd(s);
    int op, x;
    while(q--) {
        cin >> op >> x;
        if(op == 1) {
            if(vis[x]) continue;
            vis[x] = 1;
            floyd(x);
        } else {
            if(vis[x] && edge[cur][x] < INF) cout << edge[cur][x] << endl, cur = x;
            else cout << "-1" << endl;
        }
    }
    return 0;
}