fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. #define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  4. #define ll long long
  5. #define pii pair<int,int>
  6. #define pill pair<int,ll>
  7. #define pll pair<ll,ll>
  8. #define pb push_back
  9. #define fi first
  10. #define se second
  11. #define ff fi.fi
  12. #define fs fi.se
  13. #define sf se.fi
  14. #define ss se.se
  15. #define MASK(x) (((1)<<(x))-1)
  16. #define getbit(x,k) (((x)>>(k))&1)
  17.  
  18. using namespace std;
  19.  
  20. const int maxn=2e5+5,mod=1e9+7;
  21. const ll inf=1e18;
  22.  
  23. int n,m;
  24. vector<pii>eg[maxn];
  25. ll d[maxn],ans[maxn];
  26. bool id[maxn];
  27. priority_queue<pll,vector<pll>,greater<pll>>pQ;
  28.  
  29.  
  30. void dijkstra()
  31. {
  32.     while(pQ.size())
  33.     {
  34.         pll u=pQ.top();pQ.pop();
  35.         if(u.fi!=d[u.se]) continue;
  36.         for(pii v:eg[u.se]) if(u.fi+v.se<d[v.fi])
  37.         {
  38.             d[v.fi]=u.fi+v.se;
  39.             pQ.push({d[v.fi],v.fi});
  40.         }
  41.     }
  42. }
  43. void solve(int tp)
  44. {
  45.     fill(d+1,d+1+n,inf);
  46.     for(int i=1;i<=n;i++) if(id[i]==tp)
  47.     {
  48.         pQ.push({0,i});
  49.         d[i]=0;
  50.     }
  51.     dijkstra();
  52.     for(int i=1;i<=n;i++) if(d[i] && d[i]!=inf) ans[i]=d[i];
  53. }
  54. int main()
  55. {
  56.     cin>>n>>m;
  57.     for(int i=1;i<=n;i++) cin>>id[i];
  58.     for(int i=1;i<=m;i++)
  59.     {
  60.         int u,v,c;cin>>u>>v>>c;
  61.         eg[v].pb({u,c});
  62.     }
  63.     memset(ans,-1,(n+1)*sizeof(ll));
  64.     solve(0);solve(1);
  65.     for(int i=1;i<=n;i++) cout<<ans[i]<<'\n';
  66. }
  67.  
Success #stdin #stdout 0.01s 10308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/QHFCDg
language:
C++14 (gcc 8.3)
created:
4 days 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!