Znzryb's Blog
0%

Posted on Edited on

AC代码

image

我判断这道题是一道树状dp问题

以上是树状dp问题的基本思路（说白了就是递归，dfs嘛，简单）

当然我这个做法和树上dp可能还是有点不同，但都是靠子树返回的值进行计算

注释应该足够清楚，主要思路就是通过下面的节点传递上来的可传播validS进行求解，然后用dfs2打了一下链状数据结构的补丁

AC

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>

using namespace std;
typedef long long ll;
const ll N = static_cast<ll>(2e5)+10;
vector<ll> g[N];
ll n,ans,recAns;    // recAns,即rectify ans
bitset<N> vis;

// dp最重要的就是分解问题，一整颗树的求解不会，小子树的求解会不会？拼起来会不会？都会，那树上dp也就好做了
ll dfs(ll x/*,ll validS*/) {    // validS即valid start的简称，即合法的开始节点数
    // 我发现validS不需要向下传递，因为我们的求解按照遍历序，下面的点只要求解包含自己的子树就行，
    // res 表示返回值（返回的）
    ll res=0,forAns=0;      // forAns 是为了degree==3的点搞出来的
    for(int i=0;i<g[x].size();i++) {
        ll fx=g[x][i];
        if(vis[fx])
            continue;
        vis[fx]=true;
        ll acc=dfs(fx);
        if(g[x].size()==3)  // 只有degree为3的点需要考虑包含这点的环数量
            forAns+=res*acc;   // 每一个之前的合法start点都可以与acc结合，那不就是res*acc种
        res+=acc;
        // 无需回退 有一些dfs需要回退是因为怕之前的探索路径阻碍到现在的，树因为没有环，不需要担心这个问题
    }
    if(g[x].size()==2) {
        ans+=res;
        return 1;
    }
    if(g[x].size()==3) {
        ans+=forAns;
        return res;
    }
    return 0;
}

void dfs2(ll x) {   // 把链状数据剪掉，即打补丁的dfs
    for(int i=0;i<g[x].size();i++) {
        ll fx=g[x][i];
        if(vis[fx])
            continue;
        vis[fx]=true;
        if(g[fx].size()==2 && g[x].size()==2)
            recAns+=1;
        dfs2(fx);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n-1;i++) {
        ll u, v ;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vis[1]=true;
    dfs(1);
    vis.reset();
    vis[1]=true;
    dfs2(1);
    ans-=recAns;
    cout<<ans<<endl;
}
// AC https://atcoder.jp/contests/abc378/submissions/59465360

心路历程（WA，TLE，MLE……）

没过样例，主要问题在这里

degree==2的点也会阻隔validS传播

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>

using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(2e5)+10;
vector<ll> g[N];
ll n,dp[N],ans;
bitset<N> vis;

// dp最重要的就是分解问题，一整颗树的求解不会，小子树的求解会不会？拼起来会不会？都会，那树上dp也就好做了
ll dfs(ll x/*,ll validS*/) {    // validS即valid start的简称，即合法的开始节点数
    // 我发现validS不需要向下传递，因为我们的求解按照遍历序，下面的点只要包含自己的子树就行，
    // res 表示返回值（返回的）
    ll res=0,forAns=0;      // forAns 是为了degree==3的点搞出来的
    for(int i=0;i<g[x].size();i++) {
        ll fx=g[x][i];
        if(vis[fx])
            continue;
        vis[fx]=true;
        ll acc=dfs(fx);
        if(g[x].size()==3)  // 只有degree为3的点需要考虑包含这点的环数量
            forAns+=res*acc;   // 每一个之前的合法start点都可以与acc结合，那不就是res*acc种
        res+=acc;
        // 无需回退 有一些dfs需要回退是因为怕之前的探索路径阻碍到现在的，树因为没有环，不需要担心这个问题
        // if(g[fx].size()>3 || g[fx].size()<=1)
        //     res+=dfs(g[fx][i]/*,0*/);       // 不符合validS传播条件的点，阻断传播
        // else if(g[fx].size()==3)
        //     res+=dfs(g[fx][i]/*,validS*/);      // g[fx].size()==3，degree为3，可正常传播
        // else if(g[fx].size()==2)
        //     res+=dfs(g[fx][i]/*,validS+1*/);
    }
    if(g[x].size()==2) {
        ans+=res;
        return res+1;
    }
    if(g[x].size()==3) {
        ans+=forAns;
        return res;
    }
    return 0;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n-1;i++) {
        ll u, v ;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    // for(int i=1;i<=n;i++) {
    //     dp[i]=-1;
    // }
    for(int i=1;i<=n;i++) {     // 防止图不联通
        // // 我凭感觉应该是只能从degree为1的点进入，即只连了一条边点
        // if(g[i].size()>1)
        //     continue;
        if(vis[i])
            continue;
        vis[i]=true;
        dfs(i);
    }
    cout<<ans<<endl;
}

这个代码样例过了，但是全错

主要问题在于输入链状数据，答案一定为0。但我这个程序有点小问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>

using namespace std;
typedef long long ll;
const ll N = static_cast<ll>(2e5)+10;
vector<ll> g[N];
ll n,dp[N],ans;
bitset<N> vis;

// dp最重要的就是分解问题，一整颗树的求解不会，小子树的求解会不会？拼起来会不会？都会，那树上dp也就好做了
ll dfs(ll x/*,ll validS*/) {    // validS即valid start的简称，即合法的开始节点数
    // 我发现validS不需要向下传递，因为我们的求解按照遍历序，下面的点只要包含自己的子树就行，
    // res 表示返回值（返回的）
    ll res=0,forAns=0;      // forAns 是为了degree==3的点搞出来的
    for(int i=0;i<g[x].size();i++) {
        ll fx=g[x][i];
        if(vis[fx])
            continue;
        vis[fx]=true;
        ll acc=dfs(fx);
        if(g[x].size()==3)  // 只有degree为3的点需要考虑包含这点的环数量
            forAns+=res*acc;   // 每一个之前的合法start点都可以与acc结合，那不就是res*acc种
        res+=acc;
        // 无需回退 有一些dfs需要回退是因为怕之前的探索路径阻碍到现在的，树因为没有环，不需要担心这个问题
        // if(g[fx].size()>3 || g[fx].size()<=1)
        //     res+=dfs(g[fx][i]/*,0*/);       // 不符合validS传播条件的点，阻断传播
        // else if(g[fx].size()==3)
        //     res+=dfs(g[fx][i]/*,validS*/);      // g[fx].size()==3，degree为3，可正常传播
        // else if(g[fx].size()==2)
        //     res+=dfs(g[fx][i]/*,validS+1*/);
    }
    if(g[x].size()==2) {
        ans+=res;
        return 1;
    }
    if(g[x].size()==3) {
        ans+=forAns;
        return res;
    }
    return 0;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n-1;i++) {
        ll u, v ;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    // for(int i=1;i<=n;i++) {
    //     dp[i]=-1;
    // }
    for(int i=1;i<=n;i++) {     // 防止图不联通
        // // 我凭感觉应该是只能从degree为1的点进入，即只连了一条边点
        // if(g[i].size()>1)
        //     continue;
        if(vis[i])
            continue;
        vis[i]=true;
        dfs(i);
    }
    cout<<ans<<endl;
}

Posted on Edited on

AC代码

image

最主要的思想就是对前缀和进行一个预处理（即mod M）

∑1≤l≤r≤N((∑l≤i≤rAi)modM)=∑1≤l≤r≤N(Sr−Sl−1)modM, \sum_{1 \leq l \leq r \leq N} \left( \left(\sum_{l \leq i \leq r} A_i\right) \mathbin{\mathrm{mod}} M \right) = \sum_{1 \leq l \leq r \leq N} (S_r - S_{l-1}) \mathbin{\mathrm{mod}} M,

再说的透一点，就是想怎么把这个对拍程序时间复杂度最高的这部分给化简

1
2
3
4
5
for(int i=1;i<=n;i++) {
        for(int j=i;j>=1;j--) {
            ans=ans+(sumA[i]-sumA[j-1])%m;
        }
    }

这题如果你比较老实，你可能需要使用平衡树，但是你永远可以相信vector大法（虽然好像有点极限）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>

using namespace std;
typedef long long ll;
const ll N=2e5+10;
ll n,m,A[N],dp[N],ans;
ll sumA[N];         // 经过mod M预处理的前缀和数组A
ll ss[N];           // sumA[]的前缀和（即前缀和的前缀和）
vector<ll> front;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        cin>>A[i];
        sumA[i]=(sumA[i-1]+A[i])%m;
    }
    for(int i=1;i<=n;i++) {
        ss[i]=ss[i-1]+sumA[i];
    }
    for(int i=1;i<=n;i++) {
        ll dis=0;
        dis=upper_bound(front.begin(),front.end(),sumA[i])-front.begin()+1;
        // m*(i-1-dis+1) i-1为multiset的长度，-dis后要+1，故抵消
        ans=ans+(sumA[i]*i-(ss[i-1]-ss[0])+m*(i-dis));
        front.insert(lower_bound(front.begin(),front.end(),sumA[i]),sumA[i]);
    }
    cout<<ans<<endl;
}

心路历程（WA，TLE，MLE……）

对拍程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>

using namespace std;
typedef long long ll;
const ll N=2e5+10;
ll n,m,A[N],dp[N],sumA[N],ans;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        cin>>A[i];
        sumA[i]=sumA[i-1]+A[i];
    }
    for(int i=1;i<=n;i++) {
        for(int j=i;j<=n;j++) {
            ans=ans+(sumA[j]-sumA[i-1])%m;
        }
    }
    cout<<ans<<endl;
}

distance 常数太大了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>

using namespace std;
typedef long long ll;
const ll N=2e5+10;
ll n,m,A[N],dp[N],ans;
ll sumA[N];         // 经过mod M预处理的前缀和数组A
ll ss[N];           // sumA[]的前缀和（即前缀和的前缀和）
multiset<ll> front;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        cin>>A[i];
        sumA[i]=(sumA[i-1]+A[i])%m;
    }
    for(int i=1;i<=n;i++) {
        ss[i]=ss[i-1]+sumA[i];
    }
    for(int i=1;i<=n;i++) {
        ll dis=0;
        dis=distance(front.begin(),front.upper_bound(sumA[i]))+1;
        // m*(i-1-dis+1) i-1为multiset的长度，-dis后要+1，故抵消
        ans=ans+(sumA[i]*i-(ss[i-1]-ss[0])+m*(i-dis));
        front.insert(sumA[i]);
    }
    cout<<ans<<endl;
}

Posted on Edited on

AC代码

心路历程（WA，TLE，MLE……）

Posted on Edited on

AC代码

中心思想就是
// 以i点为中间点，对全部路径进行更新

只是求个最短路径的话连Path数组都不需要

AC记录

https://www.luogu.com.cn/record/186274091

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>

using namespace std;
typedef long long ll;
const ll N=110;
ll n,m,D[N][N],inf; // P[N][N];

void debug() {
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++)
            cout<<D[i][j]<<" ";
        cout<<endl;
    }
}

inline void Floyd() {
    for(int i=1;i<=n;i++) {     // 以i点为中间点，对全部路径进行更新
        for(int j=1;j<=n;j++) {
            if(j==i)           // 1->xxx node 无需更新
                continue;
            for(int k=1;k<=n;k++) {
                if(k==i)
                    continue;
                // 以i点为中间点，
                D[j][k]=min(D[j][k],D[j][i]+D[i][k]);
            }
        }
    }
    debug();
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    memset(D,0x3f,sizeof(D));       // 初始化
    inf=D[0][0];
    for(int i=1;i<=n;i++)
        D[i][i]=0;
    for(int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            P[i][j]=-1;
    for(int i=1;i<=m;i++) {
        ll u,v,w;
        cin>>u>>v>>w;
        D[u][v]=min(D[u][v],w);     // 处理一下重边与自环等特殊情况
        D[v][u]=min(D[v][u],w);
        // P[u][v]=u;      // u->v的最短路径就是u->v，存最后一个点的前驱，即u
    }
    // debug();
    // cout<<endl;
    Floyd();
}
// AC https://www.luogu.com.cn/record/186274091

心路历程（WA，TLE，MLE……）

Posted on Edited on

AC代码

时光倒流trick+floyd

注意重边处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>

using namespace std;
typedef long long ll;
const ll N=310,M=90100;
ll n,m,query,cnt,inf;                      // D里存的是到该点的最短距离（目前）
ll g[N][N],C[M];
pair<ll,ll> road[M];
vector<ll> ans;     // 逆序存储答案
struct opxy {
    ll op,x,y;
};
vector<opxy> opp;   // 就是存一下操作，实现时光倒流

// 时光倒流trick+floyd（以每个点为中间点进行的距离dp）

inline void floyd() {
    for(int i=1;i<=n;++i) {
        for(int j=1;j<=n;++j) {
            if(i==j)
                continue;
            for(int k=1;k<=n;k++) {
                if(k==i)
                    continue;
                g[j][k]=min(g[j][i]+g[i][k],g[j][k]);
            }
        }
    }
}

inline void update(ll a,ll b) {
    ll i=a;
    for(int j=1;j<=n;++j) {
        if(i==j)
            continue;
        for(int k=1;k<=n;k++) {
            if(k==i)
                continue;
            g[j][k]=min(g[j][i]+g[i][k],g[j][k]);
        }
    }
    i=b;
    for(int j=1;j<=n;++j) {     // (与上一段重复)
        if(i==j)
            continue;
        for(int k=1;k<=n;k++) {
            if(k==i)
                continue;
            g[j][k]=min(g[j][i]+g[i][k],g[j][k]);
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>query;
    memset(g,0x3f,sizeof(g));   // g初始化
    inf=g[0][0];
    for(int i=1;i<=n;++i) {
        g[i][i]=0;      // 自己到自己肯定距离为0
    }
    for(int i=1;i<=m;++i) {
        ll a,b,c;
        cin>>a>>b>>c;
        g[a][b]=min(c,g[a][b]);
        g[b][a]=min(c,g[b][a]);
        road[++cnt]=make_pair(a,b);
        C[cnt]=c;
    }
    for(int _=1;_<=query;++_) {
        int op;
        cin>>op;
        if(op==1) {
            ll idx;
            cin>>idx;
            ll a,b;
            a=road[idx].first,b=road[idx].second;
            if(g[a][b]==C[idx])
                g[a][b]=inf,g[b][a]=inf;    // 删边(处理重边情况)
            opxy lop; lop.op=1,lop.x=idx;
            opp.push_back(lop);
        }else {
            ll x,y;
            cin>>x>>y;
            opxy lop; lop.op=op,lop.x=x,lop.y=y;
            opp.push_back(lop);
        }
    }
    floyd();
    for(int i=opp.size()-1;i>=0;--i) {  // 哈哈，时光倒流启动！！！
        ll op=opp[i].op,x=opp[i].x,y=opp[i].y;
        if(op==1) {
            ll a=road[x].first,b=road[x].second;
            g[a][b]=min(C[x],g[a][b]),g[b][a]=min(C[x],g[b][a]);
            update(a,b);
        }else {
            if(g[x][y]!=inf)
                ans.push_back(g[x][y]);
            else
                ans.push_back(-1);
        }
    }
    for(int i=ans.size()-1;i>=0;--i) {
        cout<<ans[i]<<endl;
    }
}
//不知道为什么RE了好几个 https://atcoder.jp/contests/abc375/submissions/59448981
// WA 未处理重边 https://atcoder.jp/contests/abc375/submissions/59449001
// 处理了一下重边 AC https://atcoder.jp/contests/abc375/submissions/59449193

心路历程（WA，TLE，MLE……）

能跑，但是TLE，我发现这题竟然是floyd算法

需要时光倒流trick+floyd

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>

using namespace std;
typedef long long ll;
const ll N=310,M=9010;
ll n,m,query,cnt,D[N],inf;                      // D里存的是到该点的最短距离（目前）
vector<pair<ll,ll> > g[N];
pair<ll,ll> road[9010];
bool ban[N][N];
bitset<N> done;         // 存的就是dij当中已经确定的点
struct cmp {
    bool operator()(pair<ll,ll> a,pair<ll,ll> b) {
        if(a.second!=b.second)
            return a.second>b.second;       // 我们需要一个小根堆，second是存的边的长度
        return false;
    }
};
inline ll solve(ll x,ll y) {
    priority_queue<pair<ll,ll>,vector<pair<ll,ll> >, cmp> q;
    D[x]=0;
    q.push(make_pair(x,0));
    while (!q.empty()) {
        ll cdis=q.top().second,cn=q.top().first;
        q.pop();
        if(done[cn])        // 这种写法是可能会有冗余，故要判断一下
            continue;
        done[cn]=true;
        D[cn]=cdis;
        if(done[y])
            return D[y];
        for(int i=0;i<g[cn].size();i++) {
            ll fn=g[cn][i].first,fdis=g[cn][i].second+cdis;
            if(ban[cn][fn])
                continue;
            q.push(make_pair(fn,fdis));
        }
    }
    if(D[y]==inf)
        return -1;
    return D[y];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>query;
    for(int i=1;i<=m;i++) {
        ll a,b,c;
        cin>>a>>b>>c;
        g[a].push_back(make_pair(b,c));
        g[b].push_back(make_pair(a,c));
        road[++cnt]=make_pair(a,b);
    }
    for(int _=1;_<=query;_++) {
        int op;
        cin>>op;
        if(op==1) {
            ll idx;
            cin>>idx;
            ll a=road[idx].first,b=road[idx].second;
            ban[a][b]=true;ban[b][a]=true;
        }else {
            ll x,y;
            cin>>x>>y;
            memset(D,0x3f,sizeof(D));
            inf=D[0];
            done.reset();
            cout<<solve(x,y)<<endl;
        }
    }
}

WA了，可能是没有判别重边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>

using namespace std;
typedef long long ll;
const ll N=310,M=90100;
ll n,m,query,cnt,inf;                      // D里存的是到该点的最短距离（目前）
ll g[N][N],C[M];
pair<ll,ll> road[M];
vector<ll> ans;     // 逆序存储答案
struct opxy {
    ll op,x,y;
};
vector<opxy> opp;   // 就是存一下操作，实现时光倒流

// 时光倒流trick+floyd（以每个点为中间点进行的距离dp）

inline void floyd() {
    for(int i=1;i<=n;++i) {
        for(int j=1;j<=n;++j) {
            if(i==j)
                continue;
            for(int k=1;k<=n;k++) {
                if(k==i)
                    continue;
                g[j][k]=min(g[j][i]+g[i][k],g[j][k]);
            }
        }
    }
}

inline void update(ll a,ll b) {
    ll i=a;
    for(int j=1;j<=n;++j) {
        if(i==j)
            continue;
        for(int k=1;k<=n;k++) {
            if(k==i)
                continue;
            g[j][k]=min(g[j][i]+g[i][k],g[j][k]);
        }
    }
    i=b;
    for(int j=1;j<=n;++j) {     // (与上一段重复)
        if(i==j)
            continue;
        for(int k=1;k<=n;k++) {
            if(k==i)
                continue;
            g[j][k]=min(g[j][i]+g[i][k],g[j][k]);
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>query;
    memset(g,0x3f,sizeof(g));   // g初始化
    inf=g[0][0];
    for(int i=1;i<=n;++i) {
        g[i][i]=0;      // 自己到自己肯定距离为0
    }
    for(int i=1;i<=m;++i) {
        ll a,b,c;
        cin>>a>>b>>c;
        g[a][b]=c;
        g[b][a]=c;
        road[++cnt]=make_pair(a,b);
        C[cnt]=c;
    }
    for(int _=1;_<=query;++_) {
        int op;
        cin>>op;
        if(op==1) {
            ll idx;
            cin>>idx;
            ll a,b;
            a=road[idx].first,b=road[idx].second;
            g[a][b]=inf,g[b][a]=inf;    // 删边
            opxy lop; lop.op=1,lop.x=idx;
            opp.push_back(lop);
        }else {
            ll x,y;
            cin>>x>>y;
            opxy lop; lop.op=op,lop.x=x,lop.y=y;
            opp.push_back(lop);
        }
    }
    floyd();
    for(int i=opp.size()-1;i>=0;--i) {  // 哈哈，时光倒流启动！！！
        ll op=opp[i].op,x=opp[i].x,y=opp[i].y;
        if(op==1) {
            ll a=road[x].first,b=road[x].second;
            g[a][b]=C[x],g[b][a]=C[x];
            update(a,b);
        }else {
            if(g[x][y]!=inf)
                ans.push_back(g[x][y]);
            else
                ans.push_back(-1);
        }
    }
    for(int i=ans.size()-1;i>=0;--i) {
        cout<<ans[i]<<endl;
    }
}
//不知道为什么RE了好几个 https://atcoder.jp/contests/abc375/submissions/59448981