fork 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<int,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);
  45.         si(m);
  46.         si(s);
  47.         si(d);
  48.         LL ans[n+1];
  49.         //memset(ans,INF,sizeof(ans));
  50.         f(i,1,n+1) ans[i]=INF;
  51.         ans[s]=0;
  52.         bool visited[n+1];
  53.         memset(visited,false,sizeof(visited));
  54.         vector<vv> G[n+1];
  55.         int a,b,c;
  56.         f(i,0,m)
  57.         {
  58.             si(a); si(b); si(c);
  59.             G[a].pb(mp(b,c));
  60.             G[b].pb(mp(a,c));
  61.         }
  62.         int u=s;
  63.         visited[u]=true;
  64.         int p;
  65.  
  66.         while(1)
  67.         {
  68.         int j=INF,k=0;
  69.         f(i,0,G[u].size())
  70.         {
  71.             //cout<<G[u][i].first<<"\n";
  72.             if(visited[G[u][i].first]==true) continue;
  73.             k++;
  74.             ans[G[u][i].first]=min(ans[G[u][i].first],ans[u]+G[u][i].second);
  75.             if(ans[G[u][i].first]<j)
  76.             {
  77.                 j=ans[G[u][i].first];
  78.                 p=G[u][i].first;
  79.             }
  80.         }
  81.         if(k==0) break;
  82.         u=p;
  83.          visited[u]=true;
  84.          if(u==d)
  85.          {
  86.              printf("%lld\n",ans[u]);
  87.              break;
  88.          }
  89.     }
  90.     //cout<<ans[d]<<"\n";
  91.     if(ans[d]==INF)
  92.     {
  93.         printf("NONE\n");
  94.     }
  95.     }
  96.     return 0;
  97. }
  98.  
Runtime error #stdin #stdout 0.01s 2724KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/spbbgV
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!