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
Task D - Candidates of No Shortest Paths
User commy
Language C++14 (GCC 5.4.1)
Score 400
Code Size 1478 Byte
Status AC
Exec Time 7 ms
Memory 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
All 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 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