【Floyd】ABC208 D - Shortest Path Queries 2

偏执的太偏执、 2024-03-22 18:04 32阅读 0赞

[D - Shortest Path Queries 2 (atcoder.jp)][D - Shortest Path Queries 2 _atcoder.jp]

题意：

![f27d9737add1463b9888829399dbcbf7.png][]

思路：

就是模拟Floyd的过程，要边跑Floyd边统计，不然跑完再统计就不是答案了

Code：

#include <bits/stdc++.h>
    
    #define int long long
    #define max(a,b) (a>b?a:b)
    #define min(a,b) (a<b?a:b)
    
    using namespace std;
    
    const int mxn=4e2+10;
    const int mxe=3e5+10;
    const int mod=1e9+7;
    const int Inf=1e18;
    
    int N,M,u,v,w,ans=0;
    int dis[mxn][mxn];
    
    void Floyd(){
        for(int k=1;k<=N;k++){
            for(int i=1;i<=N;i++){
                for(int j=1;j<=N;j++){
                    dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
                    if(dis[i][j]<Inf/2) ans+=dis[i][j];
                }
            }
        }
    }
    void solve(){
        cin>>N>>M;
        for(int i=1;i<=N;i++){
            for(int j=1;j<=N;j++){
                if(i==j) dis[i][j]=0;
                else dis[i][j]=1e18;
            }
        }
        for(int i=1;i<=M;i++){
            cin>>u>>v>>w;
            dis[u][v]=min(dis[u][v],w);
        }
        Floyd();
        cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[D - Shortest Path Queries 2 _atcoder.jp]: https://atcoder.jp/contests/abc208/tasks/abc208_d
[f27d9737add1463b9888829399dbcbf7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/1c3176393cac44159f89a3dd9d04383c.png

发表评论取消回复

表情：

评论列表（有 0 条评论，32人围观）

还没有评论，来说两句吧...

相关阅读

相关【Floyd】ABC208 D - Shortest Path Queries 2

[D - Shortest Path Queries 2 (atcoder.jp)][D - Shortest Path Queries 2 _atcoder.jp] 题意：

偏执的太偏执、/ 2024年03月22日 18:04/ 0 赞/ 33 阅读

相关 @codechef - MGCH3D@ 3D Queries

目录 @description@ @solution@ @accepted code@ @details@ --------------------

浅浅的花香味﹌/ 2023年06月01日 13:56/ 0 赞/ 17 阅读

相关【最短路径问题（Shortest Path）——图】

最短路径问题（Shortest Path）一、最短路径（Shortest Path）二、迪杰斯特拉（Dijkstra)算法 1、Dijk

Myth丶恋晨/ 2022年12月21日 03:07/ 0 赞/ 169 阅读

相关 leetcode 304. Range Sum Query 2D - Immutable

You are given an integer array nums and you have to return a new counts array. The count

冷不防/ 2022年08月20日 13:07/ 0 赞/ 18 阅读

相关杭电5636 Shortest Path （Floyd最短路）

题目链接： [http://acm.hdu.edu.cn/showproblem.php?pid=5636][http_acm.hdu.edu.cn_showproblem

痛定思痛。/ 2022年07月27日 14:42/ 0 赞/ 131 阅读

相关 304. Range Sum Query 2D - Immutable

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by i

Bertha 。/ 2022年03月06日 06:42/ 0 赞/ 178 阅读

相关 Shortest path of the king（CodeForces - 3A）

The king is left alone on the chessboard. In spite of this loneliness, he doesn’t lose h

ゝ一世哀愁。/ 2022年01月23日 19:57/ 0 赞/ 188 阅读

相关【leetcode】1091. Shortest Path in Binary Matrix

题目如下： > In an N by N square grid, each cell is either empty (0) or blocked (1). > > A

向右看齐/ 2022年01月10日 06:13/ 0 赞/ 171 阅读

相关 Codeforces Round #580 (Div. 2) D Shortest Cycle（最小环）

题意：给你n个数，如果每两个数且（and）不为0，可以连无向边，求最小环。分析：最小环可以利用Floyd来搞，n太大，如果n很小就可以直接搞了，考虑把n缩小，因为最小

今天药忘吃喽~/ 2021年10月12日 19:24/ 0 赞/ 172 阅读

相关 [Codeforces]871D Paths

　　失踪OJ回归。　　毕竟这样的数论没做过几道，碰上一些具体的应用还是无所适从啊。小C还是借助这题大致摸索一下莫比乌斯函数吧。 Description 　　有

本是古典何须时尚/ 2021年09月29日 09:06/ 0 赞/ 309 阅读