[D] Missile Silos

우선 dijkstra 알고리즘으로 s에서 시작하여 다른 모든 정점들 까지의 최단거리를 구해놓자. dist[v] = s에서 v까지 가는 최단거리 1) 정점에 silo를 두는 경우 dist[v] == l 인 v의 개수를 세어주면 된다. 2) 간선에 silo를 두는 경우 모든 간선을 순회하면서 그 간선에 silo를 둘 수 있는지 확인할 것이다. 어떤 간선 u - v (가중치:w) 를 살펴보고 있다고 하자. 이 간선 안에 silo를 두려면 s에서 시작해 u혹은v를 거쳐 이 간선 안으로 들어왔을 때 최단거리가 l이 되는 지점이 존재해야 한다. 2-1) s에서 u를 거쳐 이 간선 안으로 들어왔을 때, 그 최단거리가 l이 되는 경우 이런 경우이려면 dist[u] < l < dist[u]+w 이면서 l <= dist[v] + (w-(l-dist[u])) 이어야 한다. 만족한다면 답에 +1 2-2) s에서 v를 거쳐 이 간선 안으로 들어왔을 때, 그 최단거리가 l이 되는 경우 이런 경우이려면 dist[v] < l < dist[v]+w 이면서 l <= dist[u] + (w-(l-dist[v])) 이어야 한다. 만족한다면 답에 +1 2-3) 2-1)도 만족하고 2-2)도 만족하는데, 그 두 지점이 사실 같은 곳인 경우 2*l == dist[v] + dist[u] + w 인 경우이다. 중복제거를 위해 답에 -1