智商被碾压

懵逼的 题目

传送至 Vijos

扯淡的 题解

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

沙茶的 代码

// 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