fork(1) download
copy 
  1. /*
  2. written by- Piyush Golani
  3. language- c++
  4. country- India
  5. College- N.I.T Jamshedpur
  6. */
  7. #include <cmath>
  8. #include <ctime>
  9. #include <iostream>
  10. #include <string>
  11. #include <vector>
  12. #include<cstdio>
  13. #include<sstream>
  14. #include<algorithm>
  15. #include<cstdlib>
  16. #include<cstring>
  17. #include<map>
  18. #include<cctype>
  19. #include<queue>
  20. using namespace std;
  21. #define pb push_back
  22. #define all(s) s.begin(),s.end()
  23. #define f(i,a,b) for(int i=a;i<b;i++)
  24. #define F(i,a,b) for(int i=a;i>=b;i--)
  25. #define PI 3.1415926535897932384626433832795
  26. #define INF 1000000005
  27. #define BIG_INF 7000000000000000000LL
  28. #define mp make_pair
  29. #define eps 1e-9
  30. #define LL long long
  31. #define si(n) scanf("%d",&n)
  32. #define sll(n) scanf("%lld",&n)
  33. #define mod 1000000007
  34. #define vv pair<LL,int>
  35.  
  36.  
  37. int main()
  38. {
  39.     int t;
  40.     si(t);
  41.     while(t--)
  42.     {
  43.         int n,m,s,d;
  44.         si(n); si(m); si(s); si(d);
  45.         vector<vv> G[n+5];
  46.         int a,b,c;
  47.         f(i,0,m)
  48.         {
  49.             si(a); si(b); si(c);
  50.             G[a].pb(mp(b,c));
  51.             G[b].pb(mp(a,c));
  52.         }
  53.         bool visited[n+5];
  54.         memset(visited,false,sizeof(visited));
  55.         LL ans[n+1];
  56.         f(i,1,n+1)
  57.         {
  58.             ans[i]=INF;
  59.         }
  60.         ans[s]=0;
  61.         priority_queue<vv,vector<vv>,greater<vv> > Q;
  62.         Q.push(mp(0,s));
  63.         while(!Q.empty())
  64.         {
  65.             vv p=Q.top();
  66.             Q.pop();
  67.             if(visited[p.second]) continue;
  68.             visited[p.second]=true;
  69.             if(p.second==d)
  70.             {
  71.                 printf("%lld\n",p.first);
  72.                 break;
  73.             }
  74.             f(i,0,G[p.second].size())
  75.             {
  76.                 int b=G[p.second][i].first;
  77.                 int c=G[p.second][i].second;
  78.                 if(!visited[b])
  79.                 {
  80.                     ans[b]=min(ans[b],ans[p.second]+c);
  81.                     Q.push(mp(ans[b],b));
  82.                 }
  83.  
  84.             }
  85.         }
  86.         if(ans[d]==INF)
  87.         {
  88.             printf("NONE\n");
  89.         }
  90.  
  91.     }
  92.     return 0;
  93. }
  94.  
  95.  
Runtime error #stdin #stdout 0s 2856KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/vi8q41
language:
C++ (gcc 8.3)
created:
11 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!