Submission #3233705


Source Code Expand

#include<iostream>
#include<vector>
using namespace std;

const int INF = 1<<29;
int d[100][100]; 

struct Edge{
    int from, to, cost;
    Edge(int f, int t, int c) : from(f), to(t), cost(c) {}
};

int main(){
    vector<Edge> v;
    for(int i = 0; i < 100; i++){
        for(int j = 0; j < 100; j++){
            d[i][j] = INF;
        }
    }

    int n, m, a, b, c;
    cin >> n >> m;

    for(int i = 0; i < m; i++){
        cin >> a >> b >> c;
        a--, b--;
        d[a][b] = d[b][a] = c;
        v.push_back(Edge(a,b,c));
    }

    for(int k = 0; k < n; k++){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(d[i][k] == INF || d[k][j] == INF)    continue;
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }

    int ans = m;

    for(Edge e : v){
        bool use = false;
        for(int s = 0; s < n; s++){
            if(d[s][e.to] == d[s][e.from] + e.cost)   use = true;
        }
        if(use) ans--;
    }

    cout << ans << endl;

    return 0;
}

Submission Info

Submission Time
Task D - Candidates of No Shortest Paths
User face4
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1105 Byte
Status WA
Exec Time 3 ms
Memory 256 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 400
Status
AC × 2
AC × 12
WA × 18
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 KB
sample_02.txt AC 1 ms 256 KB
subtask_1_01.txt AC 1 ms 256 KB
subtask_1_02.txt WA 1 ms 256 KB
subtask_1_03.txt AC 2 ms 256 KB
subtask_1_04.txt WA 2 ms 256 KB
subtask_1_05.txt WA 3 ms 256 KB
subtask_1_06.txt WA 1 ms 256 KB
subtask_1_07.txt AC 1 ms 256 KB
subtask_1_08.txt AC 2 ms 256 KB
subtask_1_09.txt AC 2 ms 256 KB
subtask_1_10.txt AC 2 ms 256 KB
subtask_1_11.txt WA 1 ms 256 KB
subtask_1_12.txt AC 2 ms 256 KB
subtask_1_13.txt AC 2 ms 256 KB
subtask_1_14.txt WA 2 ms 256 KB
subtask_1_15.txt AC 3 ms 256 KB
subtask_1_16.txt WA 1 ms 256 KB
subtask_1_17.txt WA 1 ms 256 KB
subtask_1_18.txt WA 2 ms 256 KB
subtask_1_19.txt WA 2 ms 256 KB
subtask_1_20.txt WA 1 ms 256 KB
subtask_1_21.txt WA 1 ms 256 KB
subtask_1_22.txt WA 2 ms 256 KB
subtask_1_23.txt WA 2 ms 256 KB
subtask_1_24.txt WA 3 ms 256 KB
subtask_1_25.txt WA 2 ms 256 KB
subtask_1_26.txt WA 2 ms 256 KB
subtask_1_27.txt WA 3 ms 256 KB
subtask_1_28.txt AC 3 ms 256 KB