fork(1) download
copy 
  1. #include<cstdio>
  2. #include<iostream>
  3. #include<algorithm>
  4. #include<string>
  5. #include<cstring>
  6. #include<vector>
  7. #include<stack>
  8. #include<queue>
  9. #include<deque>
  10. #include<map>
  11. #include<set>
  12. #include<limits>
  13. #include<climits>
  14. #include<cmath>
  15. #include<functional>
  16. #include<ctime>
  17. #include<cstdlib>
  18. #include<fstream>
  19. #include<typeinfo>
  20.  
  21. using namespace std;
  22.  
  23. typedef long long int ll;
  24. typedef short int i16;
  25. typedef unsigned long long int u64;
  26. typedef unsigned int u32;
  27. typedef unsigned short int u16;
  28. typedef unsigned char u8;
  29.  
  30. const int N = 150100;
  31.  
  32. const int N3 = N*3;
  33.  
  34. const int INF = 1000000000;
  35.  
  36. struct edge
  37. {
  38.     int to,w;
  39.     edge(){}
  40.     edge(int a, int b)
  41.     {
  42.         to=a;
  43.         w=b;
  44.     }
  45. };
  46.  
  47. struct el
  48. {
  49.     int vertex,cost;
  50.     el(){}
  51.     el(int a, int b)
  52.     {
  53.         vertex=a;
  54.         cost=b;
  55.     }
  56.     bool operator<(const el &a) const
  57.     {
  58.         return cost>a.cost;
  59.     }
  60. };
  61.  
  62. int a[4][N];
  63.  
  64. int n;
  65.  
  66. vector <edge> v[N3];
  67.  
  68. int dist[N3];
  69.  
  70. priority_queue <el> q;
  71.  
  72. void input() //Correct!
  73. {
  74.     scanf("%d", &n);
  75.     int i,j;
  76.     for(i=1;i<=3;i++)
  77.     {
  78.         for(j=1;j<=n;j++)
  79.         {
  80.             scanf("%d", &a[i][j]);
  81.         }
  82.     }
  83. }
  84.  
  85. void swap_rows(int r1, int r2) //Correct!
  86. {
  87.     int i;
  88.     for(i=1;i<=n;i++)
  89.     {
  90.         swap(a[r1][i],a[r2][i]);
  91.     }
  92. }
  93.  
  94. void build_graph()
  95. {
  96.     int i,j;
  97.     for(i=0;i<N3;i++)
  98.         v[i].clear();
  99.     v[0].push_back(edge(1,a[1][1]));
  100.     for(i=1;i<n;i++)
  101.     {
  102.         v[i].push_back(edge(i+1,a[1][i+1]));
  103.         v[i].push_back(edge(n+i+1,a[2][i+1]));
  104.     }
  105.     for(i=1;i<n;i++)
  106.     {
  107.         v[i+n].push_back(edge(i+n+1,a[2][i+1]));
  108.         v[i+n].push_back(edge(i+n*2+1,a[3][i+1]));
  109.     }
  110.     for(i=1;i<n;i++)
  111.     {
  112.         v[i+n*2].push_back(edge(i+n*2+1,a[3][i+1]));
  113.     }
  114. }
  115.  
  116. int Dijkstra()
  117. {
  118.     int i;
  119.     for(i=1;i<N3;i++)
  120.     {
  121.         dist[i]=INF;
  122.     }
  123.     dist[0]=0;
  124.     q.push(el(0,0));
  125.     el curr;
  126.     int current_distance;
  127.     while(!q.empty())
  128.     {
  129.         curr=q.top();
  130.         q.pop();
  131.         for(i=0;i<v[curr.vertex].size();i++)
  132.         {
  133.             current_distance=v[curr.vertex][i].w+curr.cost;
  134.             if(current_distance<dist[v[curr.vertex][i].to])
  135.             {
  136.                 dist[v[curr.vertex][i].to]=current_distance;
  137.                 q.push(el(v[curr.vertex][i].to,current_distance));
  138.             }
  139.         }
  140.     }
  141.     return dist[n*3];
  142. }
  143.  
  144. void solve()
  145. {
  146.     int ans=INF;
  147.     build_graph();
  148.     ans=min(ans,Dijkstra());
  149.     swap_rows(2,3);
  150.     build_graph();
  151.     ans=min(ans,Dijkstra());
  152.     swap_rows(2,3);
  153.  
  154.     swap_rows(1,2);
  155.     build_graph();
  156.     ans=min(ans,Dijkstra());
  157.     swap_rows(2,3);
  158.     build_graph();
  159.     ans=min(ans,Dijkstra());
  160.     swap_rows(2,3);
  161.     swap_rows(1,2);
  162.  
  163.     swap_rows(1,3);
  164.     build_graph();
  165.     ans=min(ans,Dijkstra());
  166.     swap_rows(2,3);
  167.     build_graph();
  168.     ans=min(ans,Dijkstra());
  169.     swap_rows(2,3);
  170.     swap_rows(1,3);
  171.  
  172.     printf("%d\n", ans);
  173. }
  174.  
  175.  
  176. int main()
  177. {
  178.     input();
  179.     solve();
  180.     return 0;
  181. }
  182.  
Success #stdin #stdout 0.01s 12616KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/CMXKqJ
language:
C++14 (gcc 8.3)
created:
9 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!