## current position：Home>Folyd

# Folyd

2022-08-06 08:53:19【ThXe】

```
struct Folyd {
ll mp[N][N];//i-j>最短路
ll way[N][N];//i->j有多少条不同的最短路
double ans[N];
int n, m;
void init()
{
memset(mp, 0x3f, sizeof mp);
cin >> n >> m;
while (m--)
{
int a, b, c; cin >> a >> b >> c;
mp[a][b] = c;
mp[b][a] = c;
way[a][b] = 1;
way[b][a] = 1;
}
}
void folyd()
{
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for (int j = 1; j <= n; j++)
{
if (i != j && j != k && i != k)
{
if (mp[i][j] == mp[i][k] + mp[k][j])
{
way[i][j] += way[i][k] * way[k][j];
}
else if (mp[i][j] > mp[i][k] + mp[k][j])
{
way[i][j] = way[i][k] * way[k][j];
mp[i][j] = mp[i][k] + mp[k][j];
}
}
}
}
}folyd;
```

copyright notice

author[ThXe],Please bring the original link to reprint, thank you.

https://en.chowdera.com/2022/218/202208060847341484.html

## The sidebar is recommended

- 【CF1393】D. Rarity and New Dress（dp）
- I love permutation
- Rise in Price
- Implementation of snake matrix in C language
- Educational codeforces round 116 (rated for Div. 2) e. Arena
- Complexity of two matrices
- C language: buy a hundred chickens for a hundred dollars
- [leetCode]132. Split palindrome string II
- The kth number, (the kth largest number)
- SSL 1613 shortest path problem

## guess what you like

CF1603C Extreme Extension

[winter vacation daily question] snake matrix

Internal sorting experiment

DTOJ ＃2672. Score comparison (mark)

553. Optimal division (interval DP & Mathematics)

Matrix multiplication (unresolved)

AtCoder Beginner Contest 238

[basic number theory] garlic King pour water

Notes on higher Combinatorics (nine): Twelve mode of sphere box model, generating function of partition

Disproportionated leg cutting reaction

## Random recommended

- [Blue Bridge Cup exercise] algo-479 integer sorting
- Find the smallest k elements of the array
- Print spiral matrix (C language version)
- [problem solving report] Li Kou's 284th weekly match
- Grouping knapsack problem
- Luogu p4924
- Blue Bridge Cup - matrix transpose - rotate matrix clockwise
- P3239 [hnoi2015] King Arthur (expectation)
- Luogu p2380 gouge mining [DP] [green]
- Codeforces round 735 (Div. 2) B. Cobb
- Jump game
- Leetcode question 3 - longest substring without repeated characters
- Number theory_ Block
- Workshop topic - minesweeping (Blue Bridge Cup) plus test sample
- E multiplication in the second test of Huashi Normal University
- Acwing1233. global warming
- [problem solution] [noi online 2022 improvement group] how to sort correctly
- C language - Blue Bridge Cup - basic practice matrix multiplication
- [simulation] random jump (elimination, Gauss elimination)
- Fast power 1
- 【acwing】831. KMP string*
- [game] stone game (p2599)
- Matrix multiplication implementation
- Template of n-ary linear equations
- Openjudge 1.12 09: image rotation flip transform
- Solve the generalized inverse matrix by yourself (May 4, 2022)
- 3x3 Convolution
- Minimum representation, construction and tabulation
- Prefix and (1D and 2D)
- 1224: maximum submatrix
- Luogu p3195 [hnoi2008] toy packing solution
- Find out the maximum value of each column element of NxN matrix and store it in the one-dimensional array indicated by formal parameter B in order
- 208. Switching problems
- 2022 Henan Mengxin League game (1): Henan University of technology J - Cherry transportation
- Relevant codes of difference