Submission #1056129


Source Code Expand

Copy
/*
 * Author:heroming
 * File:heroming.cpp
 * Time:2017/01/07 08:21:17
 */
#include <vector>
#include <list>
#include <set>
#include <map>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <string>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <unordered_map>
using namespace std;

#define px first
#define py second
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define clr(v, e) memset(v, e, sizeof(v))
#define rep(it, v) for (auto it : v)
#define forn(i, n) for (int i = 0; i < (n); ++ i)
#define rforn(i, n) for (int i = (n) - 1; i >= 0; -- i)
#define form(i, a, b) for (int i = (a); i <= (b); ++ i)
#define rform(i, a, b) for (int i = (b); i >= (a); -- i)
#define forv(i, v) for (int i = 0; i < sz(v); ++ i)
#define iter(it, v) for (auto it = v.begin(); it != v.end(); ++ it)

typedef long long lint;
typedef vector<int> vint;
typedef vector<string> vstring;
typedef pair<int, int> pint;
typedef vector<lint> vlint;
typedef vector<pint> vpint;

const int inf = 1e9;
const int maxn = 110;

int n, m;
int dis[maxn][maxn];
int u[maxn], v[maxn], w[maxn];

int main() {
    while (scanf("%d%d", &n, &m) != EOF) {
        form (i, 1, n) form (j, 1, n) dis[i][j] = i == j ? 0 : inf;
        forn (i, n) {
            scanf("%d%d%d", &u[i], &v[i], &w[i]);
            dis[u[i]][v[i]] = dis[v[i]][u[i]] = w[i];
        }
        form (k, 1, n) form (i, 1, n) form (j, 1, n) {
            if (dis[i][k] + dis[k][j] < dis[i][j]) {
                dis[i][j] = dis[i][k] + dis[k][j];
            }
        }
        int ans = 0;
        forn (i, n) {
            if (dis[u[i]][v[i]] < w[i]) ++ ans;
        }
        printf("%d\n", ans);
    }
    return 0;
}

Submission Info

Submission Time
Task D - Candidates of No Shortest Paths
User heroming
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1994 Byte
Status
Exec Time 115 ms
Memory 384 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:62:49: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d%d", &u[i], &v[i], &w[i]);
                                                 ^

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt
All 0 / 400 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 3 ms 256 KB
sample_02.txt 4 ms 256 KB
subtask_1_01.txt 3 ms 256 KB
subtask_1_02.txt 3 ms 256 KB
subtask_1_03.txt 113 ms 256 KB
subtask_1_04.txt 4 ms 256 KB
subtask_1_05.txt 114 ms 256 KB
subtask_1_06.txt 113 ms 256 KB
subtask_1_07.txt 3 ms 256 KB
subtask_1_08.txt 114 ms 256 KB
subtask_1_09.txt 4 ms 256 KB
subtask_1_10.txt 115 ms 256 KB
subtask_1_11.txt 113 ms 256 KB
subtask_1_12.txt 113 ms 256 KB
subtask_1_13.txt 3 ms 256 KB
subtask_1_14.txt 115 ms 384 KB
subtask_1_15.txt 3 ms 256 KB
subtask_1_16.txt 113 ms 256 KB
subtask_1_17.txt 113 ms 256 KB
subtask_1_18.txt 112 ms 256 KB
subtask_1_19.txt 113 ms 256 KB
subtask_1_20.txt 114 ms 256 KB
subtask_1_21.txt 113 ms 256 KB
subtask_1_22.txt 113 ms 256 KB
subtask_1_23.txt 113 ms 384 KB
subtask_1_24.txt 115 ms 256 KB
subtask_1_25.txt 113 ms 256 KB
subtask_1_26.txt 113 ms 256 KB
subtask_1_27.txt 115 ms 256 KB
subtask_1_28.txt 115 ms 256 KB