fork(3) download
copy 
  1. #include<bits/stdc++.h>
  2. #define pb push_back
  3. #define mp make_pair
  4. #define ff first
  5. #define ss second
  6. #define sz size()
  7. #define all(a)  a.begin(),a.end() 
  8. #define SL(n) scanf("%d",&n)
  9. #define PL(n) printf("%lld",n)
  10. #define fill(a, x) memset(a,x,sizeof(a));
  11. #define mod 1000000007
  12.  
  13. using namespace std;
  14. typedef int LL;
  15. typedef vector <LL> VL;
  16. typedef map <LL, LL> ML;
  17. typedef pair<LL, LL> PL;
  18. typedef vector <pair <LL, LL> > VPL;
  19.  
  20. int main(){
  21.     LL T;
  22.     SL(T);
  23.     LL x, y, z;
  24.     while(T--){
  25.         LL N, M;
  26.         SL(N);
  27.         SL(M);
  28.         vector<vector<LL> > Undirected;
  29.         map<pair<LL, LL>, LL> Cost;
  30.         Undirected.resize(N+5);
  31.         for(LL m=0;m<M;++m){
  32.             SL(x);
  33.             SL(y);
  34.             SL(z);
  35.             Cost[mp(x, y)] = z;
  36.             Undirected[x].pb(y);
  37.         }
  38.         LL start, end;
  39.         scanf("%d %d", &start, &end);
  40.         set<pair<LL, LL> > Q;
  41.         Q.insert(mp((LL)0, start));
  42.         bool flag = 0;
  43.         bool Vis[N+5];
  44.         LL Dist[N+5];
  45.         for(LL n=1;n<=N;++n){
  46.             Vis[n] = 0;
  47.             Dist[n] = 1e9;
  48.         }
  49.         Dist[start]  = 0;
  50.         while(Q.sz > 0){
  51.             x=Q.begin()->second;
  52.             y=Q.begin()->first;
  53.             Q.erase(Q.begin());
  54.             if(x == end) {
  55.                 flag = 1;
  56.                 break;
  57.             }
  58.             for(LL n=0;n<Undirected[x].sz;++n){
  59.                 if(Vis[Undirected[x][n]] == 0 || Vis[Undirected[x][n]] == 1 && Dist[Undirected[x][n]] > Dist[x] + Cost[mp(x, Undirected[x][n])]){//  Graph[x][Undirected[x][n]]){
  60.                     if(Vis[Undirected[x][n]] == 1){
  61.                         Q.erase(Q.find(mp(Dist[Undirected[x][n]], Undirected[x][n])));
  62.                     }
  63.                     else{
  64.                         Vis[Undirected[x][n]] = 1;
  65.                     }
  66.                     Dist[Undirected[x][n]] = Dist[x] + Cost[mp(x, Undirected[x][n])];
  67.                     Q.insert(mp(Dist[Undirected[x][n]], Undirected[x][n]));
  68.                 }
  69.             }
  70.         }
  71.         if(flag == 0){
  72.             printf("NO\n");
  73.         }
  74.         else{
  75.             printf("%d\n", Dist[end]);
  76.         }
  77.     }
  78.     return 0;
  79. }
  80.  
Runtime error #stdin #stdout #stderr 0s 3760KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/oK61Yd
language:
C++ 4.3.2 (gcc-4.3.2)
created:
8 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!