fork(2) download
  1. #include<bits/stdc++.h>
  2.  
  3. #define xx first
  4. #define yy second
  5. #define all(a) a.begin(), a.end()
  6. #define vsort(v) sort(all(v))
  7. #define UNIQUE(a) sort(all(a)); a.erase(unique(all(a)), a.end())
  8. #define clr(a,k) memset(a,k,sizeof a)
  9. #define bclr(b) memset(b,false,sizeof b)
  10. #define fr(i, a) for(i = 0; i < a; i++)
  11. #define frr(i,a) for(i = a - 1; i >= 0, i--)
  12. #define LL long long
  13. #define PB push_back
  14. #define mp make_pair
  15. ///***** bit *****///
  16. #define check_bit(a, b) (a&(1<<b))
  17. #define set_bit(a, b) (a|(1<<b))
  18. #define total_bit(a) __builtin_popcount(a)
  19. ///***** Input / Output *****///
  20. #define s1(a) scanf("%d", &a)
  21. #define s2(a, b) scanf("%d %d", &a, &b)
  22. #define s3(a, b, c) scanf("%d %d %d", &a, &b, &c)
  23. #define p1(a) printf("%d", a)
  24. #define p2(a, b) printf("%d %d", a, b)
  25. #define p3(a, b, c) printf("%d %d %d", a, b, c)
  26.  
  27. #define MOD 1000000007
  28. #define MAX 100009
  29.  
  30.  
  31. using namespace std;
  32. int n, m, s;
  33. struct Z
  34. {
  35. int v, pre;
  36. LL w;
  37. Z() {}
  38. Z(int ___, int _, LL __)
  39. {
  40. pre = ___;
  41. v = _;
  42. w = __;
  43. }
  44. bool operator < (const Z& A) const
  45. {
  46. return w > A.w;
  47. }
  48. };
  49.  
  50. map< pair< pair<int, int> , LL> , bool>M;
  51. vector<Z>V[MAX];
  52. LL dist[MAX];
  53. LL l;
  54.  
  55. bool vis[100009];
  56. LL cost[100009];
  57.  
  58. int DIJKSTRA()
  59. {
  60. for(int i = 0; i <= n; i++)
  61. dist[i] = INT_MAX, vis[i] = false;
  62.  
  63. Z tmp;
  64. tmp.v = s;
  65. tmp.w = 0;
  66. priority_queue<Z>PQ;
  67. PQ.push(tmp);
  68. int cnt = 0;
  69.  
  70. while(!PQ.empty())
  71. {
  72. tmp = PQ.top();
  73. PQ.pop();
  74. int cn = tmp.v;
  75. int pre = tmp.pre;
  76. LL cc = tmp.w;
  77. if(vis[cn]) continue;
  78. vis[cn] = true;
  79. if(cc >= l) continue;
  80.  
  81. dist[cn] = cc;
  82.  
  83. int sz = V[cn].size();
  84. for(int i = 0; i < sz; i++)
  85. {
  86. int adjn = V[cn][i].v;
  87. LL adjc = V[cn][i].w;
  88. if(adjn == pre) continue;
  89. if(adjc + cc == l)
  90. {
  91. pair < pair<int, int>, LL> P = mp(mp(adjn, adjn), 0);
  92. if(!M[P])
  93. {
  94. M[P] = true;
  95. cnt++;
  96. }
  97. continue;
  98. }
  99. else if(adjc + cc > l)
  100. {
  101. LL len = l - cc;
  102. pair < pair<int, int>, LL> P = mp(mp(cn, adjn), len);
  103. if(M[P]) continue;
  104.  
  105. LL rest = adjc - len;
  106. if(rest + cost[adjn] >= l)
  107. {
  108.  
  109. M[P] = true;
  110.  
  111. pair < pair<int, int>, LL> P1 = mp(mp(adjn, cn), rest);
  112. M[P1] = true;
  113. cnt++;
  114. }
  115. continue;
  116. }
  117. if(!vis[adjn] && adjc + cc < dist[adjn])
  118. {
  119. tmp.v = adjn;
  120. tmp.w = cc + adjc;
  121. tmp.pre = cn;
  122. PQ.push(tmp);
  123. }
  124.  
  125. }
  126. }
  127. return cnt;
  128. }
  129.  
  130.  
  131.  
  132.  
  133. void DIJKSTRA_first()
  134. {
  135. for(int i = 0; i <= n; i++)
  136. cost[i] = INT_MAX, vis[i] = false;
  137.  
  138. priority_queue<Z>PQ;
  139. Z tmp;
  140. tmp.v = s;
  141. tmp.w = 0;
  142. PQ.push(tmp);
  143.  
  144. while(!PQ.empty())
  145. {
  146. Z top = PQ.top();
  147. PQ.pop();
  148.  
  149. int cn = top.v;
  150. LL cc = top.w;
  151.  
  152. if(vis[cn]) continue;
  153. cost[cn] = cc;
  154. vis[cn] = true;
  155.  
  156. int sz = V[cn].size();
  157. for(int i = 0; i < sz; i++)
  158. {
  159. int adjn = V[cn][i].v;
  160. LL adjc = V[cn][i].w + cc;
  161. if(!vis[adjn] && adjc < cost[adjn])
  162. {
  163. tmp.v = adjn;
  164. tmp.w = adjc;
  165. cost[adjn] = adjc;
  166. PQ.push(tmp);
  167. }
  168. }
  169. }
  170. }
  171.  
  172.  
  173.  
  174.  
  175.  
  176. int main()
  177. {
  178. int tc,cs=1,i,j,k, v, u;
  179. LL w;
  180. cin>>n>>m>>s;
  181. M.clear();
  182.  
  183. fr(i, m)
  184. {
  185. cin>>u>>v>>w;
  186. V[u].PB(Z(0,v, w));
  187. V[v].PB(Z(0,u, w));
  188. }
  189.  
  190. cin>>l;
  191. DIJKSTRA_first();
  192. int res = DIJKSTRA();
  193. cout<<res<<endl;
  194.  
  195. for(i = 0; i <= n; i++)
  196. V[i].clear();
  197. return 0;
  198. }
  199.  
  200. /*
  201. //
  202.  
  203. 4 6 1
  204. 1 2 1
  205. 1 3 3
  206. 2 3 1
  207. 2 4 1
  208. 3 4 1
  209. 1 4 2
  210. 1
  211.  
  212.  
  213. */
  214.  
Success #stdin #stdout 0s 6316KB
stdin
5 6 3
3 1 1
3 2 1
3 4 1
3 5 1
1 2 6
4 5 8
4
stdout
3