Submission #5546297

Source Code Expand

#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <queue>
using namespace std;
typedef long long ll;
const ll INF = 1<<30;
const ll MOD = 1e9 + 7;
const ll MAX_N = 110;
ll G[MAX_N][MAX_N];
ll dp[MAX_N][MAX_N];
signed main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n, m; cin >> n >> m;
    for(ll i = 0; i < n; i++)
    {
        for(ll j = 0; j < n; j++) dp[i][j] = G[i][j] = INF;
    }
    for(ll i = 0; i < n; i++) dp[i][i] = G[i][i] = 0;
    for(ll i = 0; i < m; i++)
    {
        ll a, b, c; cin >> a >> b >> c;
        a--, b--;
        G[a][b] = c;
        G[b][a] = c;
        dp[a][b] = c;
        dp[b][a] = c;
    }
    for(ll k = 0; k < n; k++)
    {
        for(ll i = 0; i < n; i++)
        {
            for(ll j = 0; j < n; j++) dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
        }
    }
    // for(ll i = 0; i < n; i++)
    // {
    //     for(ll j = 0; j < n; j++) cout << setw(4) << dp[i][j]; cout << endl;
    // }
    ll ans = 0;
    for(ll i = 0; i < n; i++)
    {
        for(ll j = 0; j < n; j++)
        {
            if(G[i][j] == INF) continue;
            if(dp[i][j] != G[i][j]) ans++;
        }
    }
    cout << ans / 2 << endl;
    return 0;
}

Submission Info

Submission Time
Task D - Candidates of No Shortest Paths
User aizu_d
Language C++14 (GCC 5.4.1)
Score 400
Code Size 1409 Byte
Status AC
Exec Time 3 ms
Memory 384 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 2
AC × 30
Set Name Test Cases
Sample sample_01.txt, sample_02.txt
All sample_01.txt, sample_02.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 256 KiB
sample_02.txt AC 1 ms 256 KiB
subtask_1_01.txt AC 1 ms 256 KiB
subtask_1_02.txt AC 1 ms 384 KiB
subtask_1_03.txt AC 2 ms 384 KiB
subtask_1_04.txt AC 2 ms 384 KiB
subtask_1_05.txt AC 3 ms 384 KiB
subtask_1_06.txt AC 1 ms 384 KiB
subtask_1_07.txt AC 2 ms 384 KiB
subtask_1_08.txt AC 2 ms 384 KiB
subtask_1_09.txt AC 2 ms 384 KiB
subtask_1_10.txt AC 2 ms 384 KiB
subtask_1_11.txt AC 1 ms 384 KiB
subtask_1_12.txt AC 2 ms 384 KiB
subtask_1_13.txt AC 2 ms 384 KiB
subtask_1_14.txt AC 3 ms 384 KiB
subtask_1_15.txt AC 2 ms 384 KiB
subtask_1_16.txt AC 1 ms 256 KiB
subtask_1_17.txt AC 1 ms 256 KiB
subtask_1_18.txt AC 1 ms 384 KiB
subtask_1_19.txt AC 2 ms 384 KiB
subtask_1_20.txt AC 1 ms 256 KiB
subtask_1_21.txt AC 1 ms 256 KiB
subtask_1_22.txt AC 2 ms 384 KiB
subtask_1_23.txt AC 2 ms 384 KiB
subtask_1_24.txt AC 2 ms 384 KiB
subtask_1_25.txt AC 2 ms 384 KiB
subtask_1_26.txt AC 2 ms 384 KiB
subtask_1_27.txt AC 3 ms 384 KiB
subtask_1_28.txt AC 3 ms 384 KiB