fork(2) download
copy 
  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
comments (?)
stdin
copy 
5 6 3
3 1 1
3 2 1
3 4 1
3 5 1
1 2 6
4 5 8
4
stdout
copy 
3
https://ideone.com/6gBhHA
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!