【小码匠自习室】我真的短路了：ABC 208 - D

最短路

这道题一开始就陷入了误区，整了个5层循环，还跑过去问老码农会不会爆掉。

老码农又是华丽丽看完大神们AC的代码，然后让我过来膜拜，告诉我写的代码和大神代码区别。

本小码匠只膜拜了一眼，瞬时大悟。

老码农自然又是自夸，美其名曰：他的神来之笔，起到画龙点睛功效，让我顿悟。。。

我就不说啥了。。。

老码农，别啰嗦了，赶紧给我上下一道题。。。

题目

D - Shortest Path Queries 2
- https://atcoder.jp/contests/abc208/tasks/abc208_d

高桥王国有N座城市和M条道路。

城市编号为1到N，道路编号为1至M。道路i是一条单向道路，从城市

A_i

通向城市

B_i

，需要

C_i

分钟才能通过。

让我们将f(s，t，k)定义为以下查询的答案。

计算从城市s到城市t所需的最短时间。这里，除了城市s和t，只允许通过城市1到k。如果城市t不可访问或s=t，答案应为0。

计算所有三元组的

f(s，t，k)

，并打印它们的和。更正式地说，打印

displaystyle sum_{s = 1}^N sum_{t = 1}^N sum_{k = 1}^N f(s, t, k)

。

Constraints

1 leq N leq 400

0 leq M leq N(N-1)

1 leq A_i leq N (1 leq i leq M)

1 leq B_i leq N (1 leq i leq M)

A_i neq B_i(1 leq i leq M)

1 leq C_i leq 10^6 (1 leq i leq M)

A_i neq A_j

B_i neq B_j

, if

i neq j

输入中的所有值都是整数。

输入

vdots

输出

displaystyle sum_{s = 1}^N sum_{t = 1}^N sum_{k = 1}^N f(s, t, k)

示例输入1

代码语言：javascript复制

3 2
1 2 3
2 3 2

示例输出 1

代码语言：javascript复制

三元组s，t，k使得

f(s，t、k)neq 0

如下。

k = 1: f(1,2,1) = 3, f(2,3,1) = 2

k = 2: f(1,2,2) = 3, f(2,3,2) = 2, f(1,3,2) = 5

k = 3: f(1,2,3) = 3, f(2,3,3) = 2, f(1,3,3) = 5

示例输入 2

代码语言：javascript复制

3 0

示例输出 2

代码语言：javascript复制

对于所有的s，t，k，我们有f(s, t, k)=0。

示例输入 3

代码语言：javascript复制

示例输出 3

代码语言：javascript复制

小码匠

代码

代码语言：javascript复制

#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;
    }
    long long ans = 0;
    for (int i = 0; i < n;   i) {
        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 j = 0; j < n;   j) {
            for (int s = 0; s < n;   s) {
                if (g[j][s] < INF) {
                    ans  = g[j][s];
                }
            }
        }
    }
    cout << ans;
}
 
void happy_coder() {
}
 
int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
 
    // 小码匠
    best_coder();
 
    // 最优解
    // happy_coder();
 
    // 返回
    return 0;
}

path

0 人点赞

【小码匠自习室】我真的短路了：ABC 208 - D - Shortest Path Queries 2

最短路

题目

Constraints

输入

输出

示例输入1

示例输出 1

示例输入 2

示例输出 2

示例输入 3

示例输出 3

小码匠

代码