fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define maxx 100005
  5. #define base 36
  6. #define MOD 1003472009
  7. struct haha
  8. {
  9.     long long x, y, u, v;
  10. };
  11. struct cmp
  12. {
  13.     bool operator () (haha L, haha R)
  14.     {
  15.         return L.y>R.y;
  16.     }
  17. };
  18. long long n, m, kq=1e18, dp[maxx][2][2], d[maxx], c[maxx];
  19. vector<pair<long long, long long>> a[maxx];
  20. void build()
  21. {
  22.     priority_queue<pair<long long, int>> q;
  23.     q.push({0, n});
  24.     d[n]=0;
  25.     while(!q.empty())
  26.     {
  27.         pair<long long, int> h=q.top(); q.pop();
  28.         h.first*=(-1);
  29.         if(h.first!=d[h.second])continue;
  30.         for(auto i:a[h.second])
  31.         {
  32.             long long sum=h.first+i.second;
  33.             if(d[i.first]>sum)
  34.             {
  35.                 d[i.first]=sum;
  36.                 q.push({-sum, i.first});
  37.             }
  38.         }
  39.     }
  40. }
  41. void solve()
  42. {
  43.     priority_queue<haha, vector<haha>, cmp> q;
  44.     dp[1][0][0]=0;
  45.     dp[1][1][0]=c[1];
  46.     dp[1][0][1]=d[1];
  47.     dp[1][1][1]=c[1]+d[1];
  48.     q.push({1, dp[1][0][0], 0, 0});
  49.     q.push({1, dp[1][1][0], 1, 0});
  50.     q.push({1, dp[1][0][1], 0, 1});
  51.     q.push({1, dp[1][1][1], 1, 1});
  52.     while(!q.empty())
  53.     {
  54.         haha f=q.top(); q.pop();
  55.         if(f.y!=dp[f.x][f.u][f.v]) continue;
  56.         if(f.u&&f.v)
  57.         {
  58.             kq=min(kq, dp[f.x][f.u][f.v]);
  59.             continue;
  60.         }
  61.         for(auto i:a[f.x])
  62.         {
  63.             long long s;
  64.             for(int x=f.u; x<=1; x++)
  65.             {
  66.                 for(int y=f.v; y<=1; y++)
  67.                 {
  68.                     s=f.y+i.second;
  69.                     if(x&&!f.u) s+=c[i.first];
  70.                     if(y&&!f.v) s+=d[i.first];
  71.                     if(dp[i.first][x][y]>s)
  72.                     {
  73.                         dp[i.first][x][y]=s;
  74.                         q.push({i.first, s, x, y});
  75.                     }
  76.                 }
  77.             }
  78.         }
  79.     }
  80. }
  81. int main()
  82. {
  83.     ios_base::sync_with_stdio(0);
  84.     cin.tie(0); cout.tie(0);
  85.     cin>>n>>m;
  86.     memset(dp, 63, sizeof(dp));
  87.     memset(d, 63, sizeof(d));
  88.     for(int i=1; i<=n; i++) cin>>c[i];
  89.     for(int i=1; i<=m; i++)
  90.     {
  91.         int x, y, z;
  92.         cin>>x>>y>>z;
  93.         a[x].push_back({y, z});
  94.         a[y].push_back({x, z});
  95.     }
  96.     build();
  97.     solve();
  98.     cout<<kq;
  99.     return 0;
  100. }
  101.  
Success #stdin #stdout 0.01s 10616KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1000000000000000000
https://ideone.com/zRkpSS
language:
C++14 (gcc 8.3)
created:
8 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!