Submission #3231762

---

Source Code Expand

#include<iostream>
#include<vector>
#include<sstream>
#include<string>
#include<numeric>
using namespace std;
long input(){
  long x;
  cin>>x;
  return x;
}
int abs(int x){
  if(x>=0){
    return x;
  }else{
    return -x;
  }
}
int gcd(int x, int y){
	if(x<y){
    return gcd(y,x);
  }
  if(y==0){
    return x;
  }
  return gcd(y,x%y);
}
int cost[110][110];
int d[110];
bool used[110];
int V;
void dijkstra(int s){
  fill(d,d+V,1000000);
  fill(used,used+V,false);
  d[s]=0;
  while(true){
    int v=-1;
    for(int u=0;u<V;u++){
      if(!used[u]&&(v==-1||d[u]<d[v]))v=u;
    }
    if(v==-1)break;
    used[v]=true;
    for(int u=0;u<V;u++){
      d[u]=min(d[u],d[v]+cost[v][u]);
    }
  }

}



int main() {
  V=input();
  int M=input();
  int a[M];
  int b[M];
  int c[M];
  for(int i=0;i<M;i++){
    cin>>a[i]>>b[i]>>c[i];
    cost[a[i]][b[i]]=c[i];
  }
  int ans=M;
  for(int i=0;i<V;i++){
    bool shortest=false;
    dijkstra(i);
    for(int j=0;j<M;j++){
      if(d[a[i]+c[i]==d[b[i]]])shortest=true;
    }
    if(shortest){
      ans--;
    }


  }
  cout<<ans<<endl;



  

  




  
  
}

 

Submission Info

Judge Result