Total Highway Distance

Total Highway Distance

Description:

Little Hi and Little Ho are playing a construction simulation game. They build N cities (numbered from 1 to N) in the game and connect them by N-1 highways. It is guaranteed that each pair of cities are connected by the highways directly or indirectly.

The game has a very important value called Total Highway Distance (THD) which is the total distances of all pairs of cities. Suppose there are 3 cities and 2 highways. The highway between City 1 and City 2 is 200 miles and the highway between City 2 and City 3 is 300 miles. So the THD is 1000(200 + 500 + 300) miles because the distances between City 1 and City 2, City 1 and City 3, City 2 and City 3 are 200 miles, 500 miles and 300 miles respectively.

During the game Little Hi and Little Ho may change the length of some highways. They want to know the latest THD. Can you help them?

Input:

Line 1: two integers N and M.

Line 2 .. N: three integers u, v, k indicating there is a highway of k miles between city u and city v.

Line N+1 .. N+M: each line describes an operation, either changing the length of a highway or querying the current THD. It is in one of the following format.

EDIT i j k, indicating change the length of the highway between city i and city j to k miles.

QUERY, for querying the THD.

For 30% of the data: 2<=N<=100, 1<=M<=20

For 60% of the data: 2<=N<=2000, 1<=M<=20

For 100% of the data: 2<=N<=100,000, 1<=M<=50,000, 1 <= u, v <= N, 0 <= k <= 1000.

Output:

For each QUERY operation output one line containing the corresponding THD.

Sample input:

3 5
1 2 2
2 3 3
QUERY
EDIT 1 2 4
QUERY
EDIT 2 3 2
QUERY

Sample output:

10
14
12

分析：

   以下代码用了普通的floyd算法，复杂度是O(N3)，所以会超时，优化的代码写出来后更新。

   也欢迎各位路过的大牛们不吝赐教。

Code:

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 <stdio.h>
#include <stdlib.h>
#include <vector>
#include <map>

using namespace std;

/*
 * http://hihocoder.com/contest/hiho112/problem/1
 */

vector<map<pair<int, int>, int> > dt;

class Solution {
public:
    void queryOp(int i, int first, long long &tthd, int chd) {
        if (i <= dt.size()) {
            for (map<pair<int, int>, int>::iterator it = dt[i - 1].begin(); it != dt[i - 1].end(); it++) {
                int vv = it->first.second;
                int kk = it->second;

                if (vv != first) {
                    tthd = tthd + chd + kk;
                    queryOp(vv, i, tthd, chd + kk);
                }
            }
        }
    }

    void editOp(int i, int j, int k) {
        pair<int, int> ij = make_pair(i, j);
        dt[i - 1][ij] = k;

        pair<int, int> ji = make_pair(j, i);
        dt[j - 1][ji] = k;
    }
};

int main() {
    Solution s;
    int n, m;
    scanf("%d %d", &n, &m);
    dt = vector<map<pair<int, int>, int> >(n, map<pair<int, int>, int>());

    for (int i = 0; i < n - 1; i++) {
        int u, v, k;
        scanf("%d %d %d", &u, &v, &k);

        pair<int, int> uv = make_pair(u, v);
        dt[u - 1][uv] = k;

        pair<int, int> vu = make_pair(v, u);
        dt[v - 1][vu] = k;
    }

    for (int j = 0; j < m; j++) {
        char op[15];
        scanf("%s", op);

        if ('Q' == op[0]) {
            long long thd = 0;
            for (int i = 1; i <= dt.size(); i++) {
                long long onePointThd = 0;
                s.queryOp(i, i, onePointThd, 0);
                thd += onePointThd;
            }
            printf("%lld\n", thd / 2);
        }
        else {
            int i, j, kk;
            scanf("%d %d %d", &i, &j, &kk);

            s.editOp(i, j, kk);
        }
    }
    
    system("pause");
    return 0;
}