【小码匠自习室】主攻：数学 + 副攻：信息

小码匠

发布于 2023-03-06 14:32:22

3050

发布于 2023-03-06 14:32:22

文章被收录于专栏：小码匠和老码农

今天成果有点少

主攻：数学
- 计数原理：基础知识花了2个上午，先看课本+王后雄完全解读，一道预赛题我推了2遍，顺利AC，只是花的时间有些长。
- 挂了3道题：分层训练10道题，挂了3道，有点多啊，错题还没来的及复盘，先让妈妈给我整理到错题本了。
- 老码农晚上又给我整理了几道二项式定理的信息学题目，就不能让我闲一会吗，欺负小孩没商量。
副攻：信奥
- 01BFS：基础知识OK，老码农上来给我找的题目有些难，稍微有些晕乎，要循序渐进，别搞跨度这么大，行不行。
- 最近几天喜欢上Floyd，就让老码农给我找Floyd题目，本题ARC035-C刷的磕磕绊绊，思路完全没问题，两个角标弄错了，调试了20分钟到晚上10点才搞定，让我少看了至少半小时综艺。。。

关于Floyd

Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。

题目

C - アットコーダー王国の交通事情
- https://atcoder.jp/contests/arc035/tasks/arc035_c
翻译后题目（洛谷）
- https://www.luogu.com.cn/problem/AT_arc035_c

高桥君是 Atcoder 王国的国王。Atcoder 王国包括N个城市（编号11~N）和m条双向的道路。每条道路都有长度。对于 Atcoder 王国中的任意城市 [A,B]，都可以保证从A到B有多条道路。

高桥君认为，Atcoder人的幸福在很大程度上取决于交通的便利性。为了找出人们的幸福程度，他想找到所有可能城市之间最短路径长度的总和S。

如果城市i和j之间的最短路径的长度为 D(i,j)，则

img

高桥先生正计划建造K条新道路作为公共项目。这样的建设可能会导致多于两条或两条直接连接城市的道路，在这种情况下，现有道路将不会被拆除，而是会被增加。

您的任务是按照给定的顺序建造一条新路，并编写一个程序来计算上述每种施工的S。

输入格式：

第一行两个数n和m，分别表示城市数和道路数。接下来2~m+1行每行三个数u,v,w表示有一条连接u,v城市的长度为w的路径。第m+2行一个数k，表示有k条新的路要修建。第m+3~m+k+2行每行三个数x,y,z，表示又要建一条连接x,y的长度为z的路径。

输出格式：

输出k行，每行一个数，表示在修完第ii条道路后的S。

输入输出样例

输入 #1

输出 #1

10
8

输入 #2

输出 #2

小码匠

代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n';
 
void best_coder() {
    int n, m;
    cin >> n >> m;
    int INF = 1e9;
    vector<vector<int>> g(n, vector<int>(n, INF));
    for (int i = 0; i < m; ++i) {//存储边的情况
        int u, v, w;
        cin >> u >> v >> w;
        --u;
        --v;
        g[u][v] = w;
        g[v][u] = w;
    }
    long long ans = 0;
    for (int i = 0; i < n; ++i) {
        g[i][i] = 0;
        for (int j = 0; j < n; ++j) {
            if (j == i) {
                continue;
            }
            for (int s = 0; s < n; ++s) {
                if (s == i || s == j) {
                    continue;
                }
                g[j][s] = min(g[j][s], g[i][s] + g[j][i]);
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            ans += g[i][j];
        }
    }
    int k;
    cin >> k;
    for (int i = 0; i < k; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        --a;
        --b;
        if (c >= g[a][b]) {
            cout << ans / 2 << endl;
            continue;
        }
        ans -= 2 * (g[a][b] - c);
        g[a][b] = c;
        g[b][a] = c;
        for (int j = 0; j < n; ++j) {
            for (int s = 0; s < n; ++s) {
                int t = g[j][s];
                g[j][s] = min(g[b][s] + g[j][a] + g[a][b] , min(g[j][s], g[a][s] + g[j][b] + g[a][b]));
                ans -= t - g[j][s];
            }
        }
        cout << ans / 2 << endl;
    }
 
}
 
void happy_coder() {
}
 
int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
 
    // 小码匠
    best_coder();
 
    // 最优解
    // happy_coder();
 
    // 返回
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2023-01-27，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法