翻车笔记_ vijos2024 无向图最短路径 [Floyd]

智商被碾压

懵逼的 题目

传送至 Vijos

扯淡的 题解

比赛的时候其实想起来以前见过这道题…但没做出来…也没有什么思路…
写了四重循环大暴力还全WA…(srO李♂佬 && 马佬吊打学长)
最后怎么改都不对就看了题解(我错了TUT)…
思路其实挺简单(?)就是先把每两个点之间的边设为最短路, 然后再判断两点间是否可以松弛出一条路(即不是直接相连)和这两点之间的最短路相等, 如果有: 这两点间的直接边权就是INF, 否则就必须是最短路
然后…还错了woc???
最后发现…关了流同步, 还用了puts("")
(╯‵□′)╯︵┻━┻

沙茶的 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
// A改.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define INF (2139062143)
#define MAXN (100 + 5)
using namespace std;
int n;
int a[MAXN][MAXN];
int b[MAXN][MAXN];

void solve();
int main()
{
ios::sync_with_stdio(false);
int t;
cin >> t;
while (t--)
{

cin >> n;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
cin >> a[i][j];
}
}
solve();
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (!b[i][j])
{
cout << a[i][j] << " ";
}
else
{
cout << "infty ";
}
}
cout << endl;
}
}
return 0;
}
void solve()
{
memset(b, 0, sizeof(b));
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 && k != i)
if (a[i][k] + a[k][j] == a[i][j])
{
b[i][j]++;
}
}
}
}
}

/*
2
3
0 2 8
2 0 10
8 10 0
3
0 1 1
1 0 1
1 1 0

*/

By 药丸的 Cansult