Contest Duration: - (local time) (100 minutes) Back to Home

Submission #1056463

Source Code Expand

Copy
```#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<set>

#define REP(i,a,b) for(int i=(int)(a);i<(int)(b);++i)

using namespace std;

const int inf = 1 << 30;

struct Edge {
int next;
int cost;
int id;
Edge(int n, int c, int id) : next(n), cost(c), id(id){}
};

bool operator> (Edge e1, Edge e2) {
return e1.cost > e2.cost;
}

int main(){
int N, M;
cin >> N >> M;
vector<vector<Edge> > G(N);
REP(i, 0, M) {
int a, b, c;
cin >> a >> b >> c;
a--;
b--;
G[a].push_back(Edge(b, c, i));
G[b].push_back(Edge(a, c, i));
}

vector<int> ans(M + 1, 0);

REP (start, 0, N) {
set<int> s;
priority_queue<Edge, vector<Edge>, greater<Edge> > pq;
vector<int> isAccess(N, 0);
vector<int> cost(N, inf);
cost[start] = 0;

pq.emplace(start, 0, M);

while (pq.size()) {
Edge e = pq.top();
pq.pop();
if (isAccess[e.next]) continue;
isAccess[e.next] = 1;
s.insert(e.id);

REP (i, 0, G[e.next].size()) {
Edge ne = G[e.next][i];
if (cost[ne.next] > cost[e.next] + ne.cost) {
cost[ne.next] = cost[e.next] + ne.cost;
pq.emplace(ne.next, cost[ne.next], ne.id);
}
}
}

for (auto it = s.begin(); it != s.end(); it++) {
ans[*it]++;
}
}

int a = 0;
REP (i, 0, ans.size()) {
if (ans[i] == 0) a++;
}

cout << a << endl;

return 0;
}
```

#### Submission Info

Submission Time 2017-01-07 21:41:20+0900 D - Candidates of No Shortest Paths commy C++14 (GCC 5.4.1) 400 1478 Byte AC 7 ms 256 KB

#### Judge Result

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