常见题型快速回顾

待完成的任务：

1.用无脑的方法刷完题

2.想简单方法

3.总结：大数运算

二叉树的遍历 同类题型：1078

笨办法直接建树：

#include <cstdio>
#include <cstring>

char str[105];

struct Node {
    Node *lChild;
    Node *rChild;
    char d;
} Tree[105];
int pos;
int cur;

Node* BuildTree(int e) {
    if (str[cur] == '#' || cur >= e) return NULL;
    Tree[pos].lChild = Tree[pos].rChild = NULL;
    Node* root = &Tree[pos++];
    root->d = str[cur];
    ++cur;
    root->lChild = BuildTree(e);
    ++cur;
    root->rChild = BuildTree(e);
    return root;
}

void PrintTree(const Node* rt) {
    if(rt == NULL) return;
    if(rt->lChild != NULL) PrintTree(rt->lChild);
    printf("%c ", rt->d);
    if(rt->rChild != NULL) PrintTree(rt->rChild);
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    
    while (scanf("%s", str) != EOF) {
        pos = 0;
        cur = 0;
        Node* rt = BuildTree(strlen(str));
        PrintTree(rt);
        printf("
");
    }

    return 0;
}

或者直接模拟：

#include <cstdio>
#include <cstring>

char pre[101];
int cur;

void inOder(int e) {
    char c = pre[cur];
    if (c == '#' || cur >= e) return;
    cur++;
    inOder(e);
    printf("%c ", c);
    cur++;
    inOder(e);
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    while (scanf("%s", pre) != EOF) {
        cur = 0;
        int len = strlen(pre);
        inOder(len);
        printf("
");
    }
    return 0;
}

进制转换 

#include <cstdio>
#include <cstring>
#include <memory.h>

const int MAXN = 5000;

struct BigInt {
    int digit[MAXN];
    int size;
    
    BigInt() {
        clear();
    }

    void clear() {
        memset(digit, 0, sizeof digit);
        size = 0;
    }

    void set(int x) {
        do {
            digit[size++] = x % 10000;
            x /= 10000;
        } while(x != 0);
    }

    BigInt operator + (const BigInt &x) const {
        BigInt ret;
        int carry = 0;
        for (int i = 0; i < size || i < x.size; ++i) {
            int temp = digit[i] + x.digit[i] + carry;
            carry = temp / 10000;
            ret.digit[ret.size++] = temp % 10000;
        }
        if (carry > 0) ret.digit[ret.size++] = carry;
        return ret;
    }

    //乘以小于10000的int
    BigInt operator * (int x) const {
        BigInt ret;
        int carry = 0;
        for (int i = 0; i < size; ++i) {
            int temp = digit[i] * x + carry;
            ret.digit[ret.size++] = temp % 10000;
            carry = temp / 10000;
        }
        if (carry > 0) ret.digit[ret.size++] = carry;
        return ret;
    }

    BigInt operator / (int x) const {
        BigInt ret;
        int remainder = 0;
        for (int i = size - 1; i >= 0; --i) {
            int temp = digit[i] + remainder * 10000;
            ret.digit[i] = temp / x;
            remainder = temp % x;
        }
        //去掉末尾多余的0;
        for (int i = size - 1; i >= 0; --i) {
            ret.size = i + 1;
            if (ret.digit[i] != 0) break;
        }
        return ret;
    }

    int operator % (int x) const {
        int ret = 0;
        for (int i = size - 1; i >= 0; --i) {
            int temp = digit[i] + ret * 10000;
            ret = temp % x;
        }
        return ret;
    }

    bool isZero() {
        return size == 1 && digit[0] == 0;
    }
};

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int m, n;
    char buf[10000];
    while (scanf("%d%d", &m, &n) != EOF) {
        BigInt a;
        BigInt radix;
        a.set(0);
        radix.set(1);
        scanf("%s", buf);
        for (int i = strlen(buf) - 1; i >= 0; --i) {
            int x = 0;
            if (buf[i] >= '0' && buf[i] <= '9') 
                x = buf[i] - '0';
            else if (buf[i] >= 'a' && buf[i] <= 'z') 
                x = buf[i] - 'a' + 10;
            else
                x = buf[i] - 'A' + 10;
            a = a + radix * x;
            radix = radix * m;
        }
        
        int pos = 0;
        do {
            int x = a % n;
            a = a / n;
            if (x > 9) {
                buf[pos] = x - 10 + 'a';
            } else {
                buf[pos] = x + '0';
            }
            pos++;
        } while(!a.isZero());
        for (int i = pos - 1; i >= 0; --i) {
            printf("%c", buf[i]);
        }
        printf("
");
    }
    return 0;
}

简单计算器

投机取巧的办法：

没有括号，就不需要转换成逆波兰式。完全可以将乘法和除法先算出来，结果保存起来，然后再计算加减。

#include <cstdio>
#include <memory.h>

const int MAXN = 200;

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    char a;
    char b;
    char c;
    int t;
    while (scanf("%d%c", &t, &c) != EOF && t != 0) {
        double st[MAXN] = {0};
        int pos = 0;
        st[++pos] = t;
        while (scanf("%c%c%d%c", &a, &b, &t, &c) != EOF) {
            if (a == '+') {
                st[++pos] += t;
            } else if (a == '*') {
                st[pos] *= t;
            } else if (a == '-') {
                st[++pos] -= t;
            } else if (a == '/') {
                st[pos] /= t;
            }
            if (c == '
') break;
        }
        double ans = 0;
        for (int i = 1; i <= pos; ++i) ans += st[i];
        printf("%0.2f
", ans);
    }
    return 0;
}

正规套路：若遇到有括号和小数点的还是老老实实写个计算器吧。

#include <iostream>
#include <string>
#include <stack>

using namespace std;

int getPrior(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0;
}

string InfixToPostfix(const string &str) {
    stack<char> op;
    string ret;
    bool hasNum = false;
    bool numEnd = false;
    for (int i = 0; i < str.length(); ++i) {
        if (i == str.length() - 1) numEnd = true;
        char c = str[i];
        if (c == ' ') continue;
        if (c == '.') {
            ret.append(1, c);
            continue;
        }
        if (c <= '9' && c >= '0') {
            numEnd = false;
            hasNum = true;
            ret.append(1, c);
        }
        else {
            numEnd = true;
            if (c == '(') {
                op.push(c);
                continue;
            }
            if (c == ')') {
                while (op.top() != '(') {
                    ret.append(1, op.top());
                    op.pop();
                }
                op.pop(); // (出栈
            } else {
                if (op.empty()) op.push(c);
                else {
                    if (getPrior(c) > getPrior(op.top())) op.push(c);
                    else {
                        while (!op.empty() && getPrior(c) <= getPrior(op.top())) {
                            ret.append(1, op.top());
                            op.pop();
                        }
                        op.push(c);
                    }
                }
            }
        }
        if (numEnd && hasNum) {
            ret.append(1, ' ');
            hasNum = numEnd = false;
        }
    }
    while (!op.empty()) {
        ret.append(1, op.top());
        op.pop();
    }
    return ret;
}

//计算后缀表达式：遇到操作数就进栈，遇到操作符就出栈计算
double Calculator(const string &str) {
    stack<double> nums;
    bool hasNum = false;
    bool hasPoint = false;
    double radix = 1;
    double val = 0;
    for (int i = 0; i < str.length(); ++i) {
        char c = str[i];
        if (c == '.') {
            hasPoint = true;
            continue;
        }
        if (c <= '9' && c >= '0') {
            hasNum = true;
            if (hasPoint) {
                radix /= 10;
                val += radix * (c - '0');
            } else {
                val = val * 10 + c - '0';
            }
        } else { //遇到操作符
            if (hasNum) {
                nums.push(val);
                val = 0;
                radix = 1;
                hasNum = hasPoint = false;
            }
            if (c != '+' && c != '-' && c != '*' && c != '/') continue;
            double v1 = nums.top();
            nums.pop();
            double v2 = nums.top();
            nums.pop();
            switch (c) {
            case '+':
                v1 += v2;
                break;
            case '-':
                v1 = v2 - v1;
                break;
            case '*':
                v1 *= v2;
                break;
            case '/':
                v1 = v2 / v1;
                break;
            }
            nums.push(v1);
        }
    }
    return nums.top();
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    string str;
    while (getline(cin, str)) {
        if (str[0] == '0' && str.size() == 1) break;
        string pfix = InfixToPostfix(str);
        //cout << pfix << endl;
        printf("%0.2f
", Calculator(pfix));
    }
    return 0;
}
/*
8.3-(3.1+2*6)/5+4
4.1111 + 2.111 * (5.11 - 7) / 11
7 / 11
13 * 3 * 3
1 + 2
1 + 2
4 + 2 * 5 - 7 / 11
0
*/

浮点数加法

上次是把浮点数当做str，胡搞出来的，这次要还是继续胡搞。

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

string sum(string s1, string s2) {
    if (s1.length() < s2.length()) swap(s1, s2);
    for (int i = s1.length() - 1, j = s2.length() - 1; i >= 0; --i, --j) {
        int x = 0;
        if (j >= 0) x = s2[j] - '0';
        s1[i] += x;
        if (s1[i] > '9') {
            s1[i] -= 10;
            if (i > 0) s1[i - 1]++;
            else s1 = "1" + s1;
        }
    }
    return s1;
}

string add(string s1, string s2) {
    int p0 = 0; //结果中小数点离尾部的距离
    int p1 = s1.find('.');
    int p2 = s2.find('.');
    s1.erase(p1, 1);
    s2.erase(p2, 1);
    int len1 = s1.length() - p1;
    int len2 = s2.length() - p2;
    if (len1 > len2) { //s2末尾补0
        s2.append(len1 - len2, '0');
        p0 = len1;
    } else {
        s1.append(len2 - len1, '0');
        p0 = len2;
    }
    string ret = sum(s1, s2);
    //补上小数点，去掉末尾多余的0
    ret.insert(ret.length() - p0, ".");
    int tail = ret.find_last_not_of('0');
    return ret.substr(0, tail + 1);
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int n; 
    while (cin >> n) {
        while (n--) {
            string s1, s2;
            cin >> s1 >> s2;
            cout << add(s1, s2) << endl;
        }
    }
    return 0;
}

最大子矩阵

#include <cstdio>
#include <memory.h>

const int MAXN = 101;
int mat[MAXN][MAXN]; //表示从第i行的第j列一直向上求和，所得的单列和

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int n;
    while (scanf("%d", &n) != EOF) {
        memset(mat, 0, sizeof mat);
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                int x;
                scanf("%d", &x);
                mat[i][j] = mat[i - 1][j] + x;
            }
        }
        int ans = -1e9;
        for (int i = 1; i <= n; ++i) { //从第i行到第j行，最大递增子序列
            for (int j = i; j <= n; ++j) {
                int sum = 0;
                for (int k = 1; k <= n; ++k) {
                    int x = mat[j][k] - mat[i - 1][k]; //<i,k> <i+1,k>...<j,k>
                    if (sum > 0) sum += x;
                    else sum = x;
                    if (sum > ans) ans = sum;
                }
            }
        }
        printf("%d
", ans);
    }
    return 0;
}

最小邮票数

#include <cstdio>
#include <algorithm>

const int MAXN = 100;

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int m, n;
    while (scanf("%d%d", &m, &n) != EOF) {
        int price[20] = {0};
        for (int i = 1; i <= n; ++i) 
            scanf("%d", &price[i]);
        int dp[MAXN]; //前i种邮票拼出面值m的最小张数
        for (int j = 0; j <= m; ++j) {
            dp[j] = 1e9;
        }
        dp[0] = 0;
        for (int i = 1; i <= n; ++i) 
            for (int j = m; j >= price[i]; --j) 
                dp[j] = std::min(dp[j], dp[j - price[i]] + 1);
        if (dp[m] == 1e9) puts("0");
        else printf("%d
", dp[m]);
    }
    return 0;
}

最短路径问题 

#include <cstdio>

const int MAXN = 1001;
const int INF = 1e9;

int arc[MAXN][MAXN];
int epn[MAXN][MAXN];
int dist[MAXN];
int cost[MAXN];

void init() {
    for (int i = 0; i < MAXN; ++i) 
        for (int j = 0; j < MAXN; ++j) 
            arc[i][j] = epn[i][j] = INF;
}

void dijsktra(int a, int n) {
    bool s[MAXN] = {false};
    for (int i = 1; i <= n; ++i) {
        dist[i] = arc[a][i];
        cost[i] = epn[a][i];
    }
    dist[a] = cost[a] = 0;
    s[a] = true;
    for (int i = 1; i < n; ++i) {
        int tmp = INF;
        int m = a;
        for (int j = 1; j <= n; ++j) {
            if (!s[j] && tmp > dist[j]) {
                tmp = dist[j];
                m = j;
            }
        }
        s[m] = true;
        for (int j = 1; j <= n; ++j) {
            if (s[j]) continue; 
            int d = dist[m] + arc[m][j];
            int c = cost[m] + epn[m][j];
            if (d < dist[j] || d == dist[j] && cost[j] < c) {
                dist[j] = d;
                cost[j] = c;
            } 
        }
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int n, m;
    while (scanf("%d%d", &n, &m) != EOF && (n != 0 || m != 0)) {
        init();
        while (m--) {
            int a, b, d, p;
            scanf("%d%d%d%d", &a, &b, &d, &p);
            arc[a][b] = arc[b][a] = d;
            epn[a][b] = epn[b][a] = p;
        }
        int s, e;
        scanf("%d%d", &s, &e);
        dijsktra(s, n);
        printf("%d %d
", dist[e], cost[e]);
    }
    return 0;
}

孤岛连通工程

#include <cstdio>
#include <memory.h>
#include <algorithm>

const int MAXN = 1001;
const int INF = 1e9;

int Tree[MAXN];

int findRoot(int x) {
    if (Tree[x] == 0) return x;
    int ret = findRoot(Tree[x]);
    Tree[x] = ret;
    return ret;
}

struct A {
    int a, b;
    int w;
} arc[10001];

bool operator < (const A &a1, const A &a2) {
    return a1.w < a2.w;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int n, m;
    while (scanf("%d%d", &n, &m) != EOF) {
        memset(Tree, 0, sizeof Tree);
        for (int i = 0; i < m; ++i) {
            scanf("%d%d%d", &arc[i].a, &arc[i].b, &arc[i].w);
        }
        std::sort(arc, arc + m);
        int d = 0;
        for (int i = 0; i < m; ++i) {
            int a = findRoot(arc[i].a);
            int b = findRoot(arc[i].b);
            if (a != b) {
                Tree[a] = b;
                d += arc[i].w;
            }
        }
        int num = 0;
        for (int i = 1; i <= n; ++i) {
            if (Tree[i] == 0) ++num;
        }
        if (num != 1) puts("no");
        else printf("%d
", d);
    }
    return 0;
}

哈夫曼树

#include <cstdio>
#include <queue>
#include <functional>

using namespace std;

priority_queue<int, vector<int>, greater<int> > q;

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int n;
    while (scanf("%d", &n) != EOF) {
        while (!q.empty()) q.pop();
        while (n--) {
            int a;
            scanf("%d", &a);
            q.push(a);
        }
        //乘积之和等于除根结点之外的各结点的和
        int ans = 0;
        while (q.size() > 1) { 
            int a = q.top();
            q.pop();
            int b = q.top();
            q.pop();
            ans += a + b;
            q.push(a + b);
        }
        printf("%d
", ans);
    }
    return 0;
}

全排列

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif 
    char str[7];
    while (scanf("%s", str) != EOF) {
        int len = strlen(str);
        do {
            printf("%s
", str);
        } while(next_permutation(str, str + len));
        printf("
");    
    }
    return 0;
}

如果不会拼写permutation，那就只能dfs了：

#include <cstdio>
#include <cstring>
#include <memory.h>

bool mark[7];
char str[7];
char buf[7];
int len;

void dfs(int pos) {
    if (pos == len) {
        buf[pos] = 0;
        printf("%s
", buf);
        return;
    }
    for (int i = 0; i < len; ++i) {
        if (!mark[i]) {
            mark[i] = true;
            buf[pos] = str[i];
            dfs(pos + 1);
            mark[i] = false;
        }
    }
    
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    while (scanf("%s", str) != EOF) { //由于测试数据的原因，这里用gets会越界！？
        memset(mark, false, sizeof mark);
        len = strlen(str);
        dfs(0);
        printf("
");
    }
    return 0;
}

八皇后

#include <cstdio>
#include <memory.h>
#include <cstdlib>

int output[93][9];
int queen[9];
int num;

bool check(int k, int p) { //第k个皇后能否放在位置p
    for (int i = 1; i < k; ++i) {
        if (queen[i] == p || abs(k - i) == abs(queen[i] - p))
            return false;
    }
    return true;
}

void dfs(int k) {
    if (k == 9) {
        num++;
        for (int i = 1; i <= 8; ++i) output[num][i] = queen[i];
    }
    for (int i = 1; i <= 8; ++i) {
        if (check(k, i)) {
            queen[k] = i;
            dfs(k + 1);
        }
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    num = 0;
    memset(queen, 0, sizeof queen);
    dfs(1);
    int n;
    while (scanf("%d", &n) != EOF) {
        while (n--)    {
            int a;
            scanf("%d", &a);
            for (int i = 1; i <= 8; ++i) 
                printf("%d", output[a][i]);
            printf("
");
        }
    }
    return 0;
}

棋盘游戏

首先想到的是直接无脑BFS，结果错惨了，这题的代价是由状态确定的，也就说做不同的路径到达同一点会产生不同的代价，后面再次搜到某个点，可能会产生更小的代价，因此不能简单的用个mark数组来剪枝，棋盘比较小可以保存每个坐标的代价来剪枝。

#include <cstdio>
#include <queue>
#include <functional>
#include <memory.h>

using namespace std;

int go[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
int maze[8][8];
int cost[8][8][5];//状态<i,j,w>对应的代价

struct E {
    int a, b;
    int w;//状态
    int t;//代价
    bool operator > (const E &e) const {
        return t > e.t;
    }
};

priority_queue<E, vector<E>, greater<E> > Q;

//注意：由于到达的时候，状态值可以不同，从而导致代价不同，所以已搜索到的点可以再次被从其他线路搜索
int BFS(int e1, int e2) {
    int ans = 1e9;
    while (!Q.empty()) {
        E ne = Q.top();
        Q.pop();
        if (ne.a == e1 && ne.b == e2) {
            if (ans > ne.t) ans = ne.t;
        }
        for (int i = 0; i < 4; ++i) {
            int a = ne.a + go[i][0];
            int b = ne.b + go[i][1];
            if (maze[a][b] != 0) {
                int t = ne.w * maze[a][b];
                int w = t % 4 + 1;
                if (cost[a][b][w] == -1 || cost[a][b][w] > ne.t + t) {
                    E s;
                    s.a = a;
                    s.b = b;
                    s.t = ne.t + t;
                    s.w =  w;
                    cost[a][b][w] = s.t;
                    Q.push(s);
                }
            }
        }
    }
    return ans;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int n;
    scanf("%d", &n);
    while (n--) {
        while (!Q.empty()) Q.pop();
        memset(maze, 0, sizeof maze);
        memset(cost, -1, sizeof cost);
        for (int i = 1; i <= 6; ++i) 
            for (int j = 1; j <= 6; ++j) 
                scanf("%d", &maze[i][j]);
        int s1, s2, e1, e2;
        scanf("%d%d%d%d", &s1, &s2, &e1, &e2);
        E s;
        s.a = s1 + 1;
        s.b = s2 + 1;
        s.w = 1;
        s.t = 0;
        cost[s1 + 1][s2 + 1][1] = 0;
        Q.push(s);
        printf("%d
", BFS(e1 + 1, e2 + 1));
    }
    return 0;
}

DFS解法：通过DFS解法可以看出，OJ上的标程有问题。每一步的代价至少为1，也就是说没理由会出现再次经过起点的重复路径，应该将出发点mark[sx][sy]标记为true，但这样就没法AC了，能AC的代码如下，起点要当做没被访问的点，后面会再次搜到起点，也就是说答案中有数据的最小代价的路径是从起点出发并再次经过起点？实在想出来这是什么样的一种情况。

#include <cstdio>
#include <memory.h>

int go[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};

int maze[8][8];
bool mark[8][8];
int e1, e2;
int ans;

void DFS(int x, int y, int status, int cost) {
    if (cost >= ans) return;
    if (x == e1 && y == e2) {
        ans = cost;
        return;
    }
    for (int i = 0; i < 4; ++i) {
        int na = x + go[i][0];
        int nb = y + go[i][1];
        if (maze[na][nb] != 0 && !mark[na][nb]) {
            mark[na][nb] = true;
            int t = status * maze[na][nb];
            DFS(na, nb, t % 4 + 1, t + cost);
            mark[na][nb] = false;
        }
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int n;
    scanf("%d", &n);
    while (n--) {
        memset(maze, 0, sizeof maze);
        memset(mark, false, sizeof mark);
        ans = 1e9;
        for (int i = 1; i <= 6; ++i) 
            for (int j = 1; j <= 6; ++j) 
                scanf("%d", &maze[i][j]);
        int s1, s2;
        scanf("%d%d%d%d", &s1, &s2, &e1, &e2);
        e1 += 1;
        e2 += 1;
        DFS(s1 + 1, s2 + 1, 1, 0);
        printf("%d
", ans);
    }
    return 0;
}

2的幂次方

#include <cstdio>
#include <string>

int pow2[15];

void init() {
    int r = 1;
    for (int i = 0; i < 15; ++i) {
        pow2[i] = r;
        r *= 2;
    }
}

void output(int n) {
    if (n == 0) {
        printf("0");
        return; 
    }
    bool first = true;
    for (int i = 14; i >= 0; --i) {
        if (n >= pow2[i]) {
            if (!first) printf("+");
            printf("2");
            first = false;
            n -= pow2[i];
            if (pow2[i] != 2) {
                printf("(");
                output(i);
                printf(")");
            }
        }
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int n;
    init();
    while (scanf("%d", &n) != EOF) {
        output(n);
        printf("
");
    }
    return 0;
}

城际公路网

这道题每次更新边之后，不需要再用floyd把所有的边更新一次，只需通过新增的变更新其他的点的距离：arc[i][j] = min(arc[i][j], arc[i][a] + arc[a][b] + arc[b][j]);

#include <cstdio>

const int MAXN = 301;
int arc[MAXN][MAXN];

void update(int a, int b, int n, int w) {
    for (int i = 1; i <= n; ++i) 
        for (int j = 1; j <= n; ++j) {
            int d = arc[i][a] + w + arc[b][j];
            if (d < arc[i][j]) 
                arc[i][j] = arc[j][i] = d;
        }
}

int dist(int n) {
    int sum = 0;
    for (int i = 1; i <= n; ++i) 
        for (int j = 1; j < i; ++j) 
            sum += arc[i][j];
    return sum;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int n;
    while (scanf("%d", &n) != EOF) {
        for (int i = 1; i <= n; ++i) 
            for (int j = 1; j <= n; ++j) 
                scanf("%d", &arc[i][j]);
        int k;
        scanf("%d", &k);
        int ans = dist(n);
        while (k--) {
            int a, b, w;
            scanf("%d%d%d", &a, &b, &w);
            if (w < arc[a][b]) { //更新其他的公路
                update(a, b, n, w);
                ans = dist(n);
            }
            printf("%d
", ans);
        }
    }
    return 0;
}