fork download
  1. #include <iostream>
  2. using namespace std;
  3. #include<bits/stdc++.h>
  4. //graph bfs
  5. int main() {
  6. // your code goes here
  7. int n ; int m ;
  8. cin>>n>>m;
  9. vector<vector<int>>adj(n+1);
  10. vector<bool>vis(n+1,false);
  11. int level[n+1];
  12. for(int i = 0 ; i < m ; i++){
  13. int u ; int v ;
  14. cin>>u>>v;
  15. adj[u].push_back(v);
  16. adj[v].push_back(u);
  17. }
  18. queue<int>q;
  19. int src;int dest;
  20. cin>>src>>dest;
  21. int val[n+1];
  22. for(int i = 1; i<=n;i++){
  23. cin>>val[i];
  24. }
  25. q.push(src);
  26. vis[src]=true;
  27. level[src]=0; int count = 0 ;
  28.  
  29. int C[n+1]={0};
  30. C[src]=1;
  31. int max5[n+1]={0};
  32. max5[src]=val[src];
  33. while(!q.empty()){
  34. int curr = q.front();
  35. q.pop();
  36.  
  37. for(auto adjacent : adj[curr]){
  38. if(!vis[adjacent]){
  39. vis[adjacent]= true;
  40. q.push(adjacent);
  41. level[adjacent]=level[curr]+1;
  42. }
  43. if(level[adjacent]-level[curr]==1) {
  44. if(max5[curr]+val[adjacent]>max5[adjacent]){
  45. max5[adjacent]= max5[curr]+val[adjacent];
  46. C[adjacent] = C[curr];
  47. }
  48. else if(max5[curr]+val[adjacent]==max5[adjacent]){
  49. C[adjacent]+=C[curr];
  50. }
  51. }
  52. }
  53.  
  54. }
  55. cout<<C[dest];
  56.  
  57.  
  58. return 0;
  59. }
Success #stdin #stdout 0.01s 5320KB
stdin
8 9 
1 2 
2 3
3 4
1 5
5 6
6 4
1 7 
7 8 
8 4
1 4
0 5 5 0 5 5 0 0 
stdout
2