API tools faq
paste
Advertisement
Guest User

euler 18 dijkstra

a guest
Apr 16th, 2017
569
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 14.53 KB | None | 0 0
raw download clone embed print report
  1. #include<iostream>
  2. #include<queue>
  3. #include<list>
  4. #include<stack>
  5.  
  6.  
  7. using namespace std;
  8.  
  9. typedef struct node
  10. {
  11.     int index;
  12.     int value;
  13.     int bestValue;
  14.     bool operator < (const node &lhs)
  15.     {
  16.         return 0;
  17.     }
  18. }node;
  19. node createNode(int index, int value)
  20. {
  21.     node temp;
  22.     temp.index = index;
  23.     temp.value = value;
  24.     temp.bestValue = temp.value;
  25.     return temp;
  26. }
  27.  
  28. node dfsCount = createNode(0,0);
  29.  
  30. class graph
  31. {
  32.  
  33.     list<node> *totalVertex;
  34.     int vertex;
  35.  
  36.  
  37. public:
  38.    
  39.  
  40.     graph(int vertex)
  41.     {
  42.         this->vertex = vertex;
  43.         totalVertex = new list<node>[vertex];
  44.        
  45.     }
  46.  
  47.     void addEdge(node position, node value)
  48.     {
  49.         totalVertex[position.index].push_back(value);
  50.     }
  51.    
  52.  
  53.    
  54.     int BFS(node startpos)
  55.     {
  56.        
  57.         bool hasChild =false;
  58.  
  59.    
  60.         list<node> queue;
  61.         list<int>queuesum;
  62.         int sum=0;
  63.         int pushValue;
  64.        
  65.         int smallestValue = 20000;
  66.        
  67.         queue.push_back(startpos);
  68.         queuesum.push_back(startpos.value);
  69.            
  70.    
  71.         list<node>::iterator i;
  72.    
  73.        
  74.         while (!queue.empty())
  75.         {
  76.             hasChild = false;
  77.            
  78.             startpos = queue.front();
  79.             sum = queuesum.front();
  80.            
  81.             queue.pop_front();
  82.             queuesum.pop_front();
  83.            
  84.        
  85.         for (i = totalVertex[startpos.index].begin(); i != totalVertex[startpos.index].end(); ++i)
  86.             {
  87.                 hasChild = true;
  88.  
  89.  
  90.                 pushValue = i->value+ sum;
  91.  
  92.  
  93.                 queuesum.push_back(pushValue);
  94.  
  95.                 queue.push_back(*i);
  96.             }
  97.             if (!hasChild)
  98.             {
  99.  
  100.                 if (sum < smallestValue)
  101.                 {
  102.                     smallestValue = sum;
  103.        
  104.                    
  105.                 }
  106.            
  107.             }
  108.        
  109.  
  110.            
  111.         }
  112.  
  113.         return smallestValue;
  114.     }
  115.  
  116.     int dijkstraBFS(node startpos)
  117.     {
  118.  
  119.         bool hasChild = false;
  120.  
  121.  
  122.         priority_queue<node> queue;
  123.         priority_queue<int>queuesum;
  124.         int sum = 0;
  125.         int pushValue;
  126.  
  127.         int smallestValue = 20000;
  128.  
  129.         queue.push(startpos);
  130.         queuesum.push(startpos.value);
  131.  
  132.  
  133.         list<node>::iterator i;
  134.  
  135.  
  136.         while (!queue.empty())
  137.         {
  138.             hasChild = false;
  139.  
  140.             startpos = queue.top();
  141.             sum = queuesum.top();
  142.  
  143.             queue.pop();
  144.             queuesum.pop();
  145.  
  146.  
  147.             for (i = totalVertex[startpos.index].begin(); i != totalVertex[startpos.index].end(); ++i)
  148.             {
  149.                 hasChild = true;
  150.  
  151.  
  152.                 pushValue = i->value + sum;
  153.  
  154.  
  155.                 queuesum.push(pushValue);
  156.  
  157.                 queue.push(*i);
  158.             }
  159.             if (!hasChild)
  160.             {
  161.  
  162.                 if (sum < smallestValue)
  163.                 {
  164.                     smallestValue = sum;
  165.  
  166.  
  167.                 }
  168.  
  169.             }
  170.  
  171.  
  172.  
  173.         }
  174.  
  175.         return smallestValue;
  176.     }
  177.  
  178.  
  179. } ;
  180.  
  181.  
  182.  
  183.  
  184.  
  185. int main()
  186. {
  187.     int finalValue=0;
  188.  
  189.    
  190.  
  191.     graph triangle(120);
  192.     //row 0
  193.     node node0 = createNode(0, 75);
  194.  
  195.     //row 1
  196.     node node1 = createNode(1, 95);
  197.     node node2 = createNode(2, 64);
  198.  
  199.     //row 3
  200.     node node3 = createNode(3, 17);
  201.     node node4 = createNode(4, 47);
  202.     node node5 = createNode(5, 82);
  203.  
  204.     //row 4
  205.     node node6 = createNode(6, 18);
  206.     node node7 = createNode(7, 35);
  207.     node node8 = createNode(8, 87);
  208.     node node9 = createNode(9, 10);
  209.  
  210.     //row 5
  211.     node node10 = createNode(10, 20);
  212.     node node11 = createNode(11, 4);
  213.     node node12 = createNode(12, 82);
  214.     node node13 = createNode(13, 47);
  215.     node node14 = createNode(14, 65);
  216.  
  217.     //row 6
  218.     node node15 = createNode(15, 19);
  219.     node node16 = createNode(16, 1);
  220.     node node17 = createNode(17, 23);
  221.     node node18 = createNode(18, 75);
  222.     node node19 = createNode(19, 3);
  223.     node node20 = createNode(20, 34);
  224.  
  225.     //row 7
  226.     node node21 = createNode(21, 88);
  227.     node node22 = createNode(22, 2);
  228.     node node23 = createNode(23, 77);
  229.     node node24 = createNode(24, 73);
  230.     node node25 = createNode(25, 7);
  231.     node node26 = createNode(26, 63);
  232.     node node27 = createNode(27, 67);
  233.  
  234.     //row 8
  235.     node node28 = createNode(28, 99);
  236.     node node29 = createNode(29, 65);
  237.     node node30 = createNode(30, 4);
  238.     node node31 = createNode(31, 28);
  239.     node node32 = createNode(32, 6);
  240.     node node33 = createNode(33, 16);
  241.     node node34 = createNode(34, 70);
  242.     node node35 = createNode(35, 92);
  243.  
  244.     //row 9
  245.     node node36 = createNode(36, 41);
  246.     node node37 = createNode(37, 41);
  247.     node node38 = createNode(38, 26);
  248.     node node39 = createNode(39, 56);
  249.     node node40 = createNode(40, 83);
  250.     node node41 = createNode(41, 40);
  251.     node node42 = createNode(42, 80);
  252.     node node43 = createNode(43, 70);
  253.     node node44 = createNode(44, 33);
  254.  
  255.     //row 10
  256.     node node45 = createNode(45, 41);
  257.     node node46 = createNode(46, 48);
  258.     node node47 = createNode(47, 72);
  259.     node node48 = createNode(48, 33);
  260.     node node49 = createNode(49, 47);
  261.     node node50 = createNode(50, 32);
  262.     node node51 = createNode(51, 37);
  263.     node node52 = createNode(52, 16);
  264.     node node53 = createNode(53, 94);
  265.     node node54 = createNode(54, 29);
  266.  
  267.     //row 11
  268.     node node55 = createNode(55, 53);
  269.     node node56 = createNode(56, 71);
  270.     node node57 = createNode(57, 44);
  271.     node node58 = createNode(58, 65);
  272.     node node59 = createNode(59, 25);
  273.     node node60 = createNode(60, 43);
  274.     node node61 = createNode(61, 91);
  275.     node node62 = createNode(62, 52);
  276.     node node63 = createNode(63, 97);
  277.     node node64 = createNode(64, 51);
  278.     node node65 = createNode(65, 14);
  279.  
  280.     //row 12
  281.     node node66 = createNode(66, 70);
  282.     node node67 = createNode(67, 11);
  283.     node node68 = createNode(68, 33);
  284.     node node69 = createNode(69, 28);
  285.     node node70 = createNode(70, 77);
  286.     node node71 = createNode(71, 73);
  287.     node node72 = createNode(72, 17);
  288.     node node73 = createNode(73, 78);
  289.     node node74 = createNode(74, 39);
  290.     node node75 = createNode(75, 68);
  291.     node node76 = createNode(76, 17);
  292.     node node77 = createNode(77, 57);
  293.  
  294.     //row 13
  295.     node node78 = createNode(78, 91);
  296.     node node79 = createNode(79, 71);
  297.     node node80 = createNode(80, 52);
  298.     node node81 = createNode(81, 38);
  299.     node node82 = createNode(82, 17);
  300.     node node83 = createNode(83, 14);
  301.     node node84 = createNode(84, 91);
  302.     node node85 = createNode(85, 43);
  303.     node node86 = createNode(86, 58);
  304.     node node87 = createNode(87, 50);
  305.     node node88 = createNode(88, 27);
  306.     node node89 = createNode(89, 29);
  307.     node node90 = createNode(90, 48);
  308.  
  309.  
  310.     //row 14
  311.     node node91 = createNode(91, 63);
  312.     node node92 = createNode(92, 66);
  313.     node node93 = createNode(93, 4);
  314.     node node94 = createNode(94, 68);
  315.     node node95 = createNode(95, 89);
  316.     node node96 = createNode(96, 53);
  317.     node node97 = createNode(97, 67);
  318.     node node98 = createNode(98, 30);
  319.     node node99 = createNode(99, 73);
  320.     node node100 = createNode(100, 16);
  321.     node node101 = createNode(101, 69);
  322.     node node102 = createNode(102, 87);
  323.     node node103 = createNode(103, 40);
  324.     node node104 = createNode(104, 31);
  325.  
  326.     //row 15
  327.     node node105 = createNode(105, 4);
  328.     node node106 = createNode(106, 62);
  329.     node node107 = createNode(107, 98);
  330.     node node108 = createNode(108, 27);
  331.     node node109 = createNode(109, 23);
  332.     node node110 = createNode(110, 9);
  333.     node node111 = createNode(111, 70);
  334.     node node112 = createNode(112, 98);
  335.     node node113 = createNode(113, 73);
  336.     node node114 = createNode(114, 93);
  337.     node node115 = createNode(115, 38);
  338.     node node116 = createNode(116, 53);
  339.     node node117 = createNode(117, 60);
  340.     node node118 = createNode(118, 4);
  341.     node node119 = createNode(119, 23);
  342.  
  343.    
  344.     triangle.addEdge(node0, node1);
  345.     triangle.addEdge(node0, node2);
  346.  
  347.     triangle.addEdge(node1, node3);
  348.     triangle.addEdge(node1, node4);
  349.     triangle.addEdge(node2, node4);
  350.     triangle.addEdge(node2, node5);
  351.  
  352.     triangle.addEdge(node3, node6);
  353.     triangle.addEdge(node3, node7);
  354.     triangle.addEdge(node4, node7);
  355.     triangle.addEdge(node4, node8);
  356.     triangle.addEdge(node5, node8);
  357.     triangle.addEdge(node5, node9);
  358.  
  359.     triangle.addEdge(node6, node10);
  360.     triangle.addEdge(node6, node11);
  361.     triangle.addEdge(node7, node11);
  362.     triangle.addEdge(node7, node12);
  363.     triangle.addEdge(node8, node12);
  364.     triangle.addEdge(node8, node13);
  365.     triangle.addEdge(node9, node13);
  366.     triangle.addEdge(node9, node14);
  367.  
  368.     triangle.addEdge(node10, node15);
  369.     triangle.addEdge(node10, node16);
  370.     triangle.addEdge(node11, node16);
  371.     triangle.addEdge(node11, node17);
  372.     triangle.addEdge(node12, node17);
  373.     triangle.addEdge(node12, node18);
  374.     triangle.addEdge(node13, node18);
  375.     triangle.addEdge(node13, node19);
  376.     triangle.addEdge(node14, node19);
  377.     triangle.addEdge(node14, node20);
  378.  
  379.     triangle.addEdge(node15, node21);
  380.     triangle.addEdge(node15, node22);
  381.     triangle.addEdge(node16, node22);
  382.     triangle.addEdge(node16, node23);
  383.     triangle.addEdge(node17, node23);
  384.     triangle.addEdge(node17, node24);
  385.     triangle.addEdge(node18, node24);
  386.     triangle.addEdge(node18, node25);
  387.     triangle.addEdge(node19, node25);
  388.     triangle.addEdge(node19, node26);
  389.     triangle.addEdge(node20, node26);
  390.     triangle.addEdge(node20, node27);
  391.  
  392.     triangle.addEdge(node21, node28);
  393.     triangle.addEdge(node21, node29);
  394.     triangle.addEdge(node22, node29);
  395.     triangle.addEdge(node22, node30);
  396.     triangle.addEdge(node23, node30);
  397.     triangle.addEdge(node23, node31);
  398.     triangle.addEdge(node24, node31);
  399.     triangle.addEdge(node24, node32);
  400.     triangle.addEdge(node25, node32);
  401.     triangle.addEdge(node25, node33);
  402.     triangle.addEdge(node26, node33);
  403.     triangle.addEdge(node26, node34);
  404.     triangle.addEdge(node27, node34);
  405.     triangle.addEdge(node27, node35);
  406.  
  407.     triangle.addEdge(node28, node36);
  408.     triangle.addEdge(node28, node37);
  409.     triangle.addEdge(node29, node37);
  410.     triangle.addEdge(node29, node38);
  411.     triangle.addEdge(node30, node38);
  412.     triangle.addEdge(node30, node39);
  413.     triangle.addEdge(node31, node39);
  414.     triangle.addEdge(node31, node40);
  415.     triangle.addEdge(node32, node40);
  416.     triangle.addEdge(node32, node41);
  417.     triangle.addEdge(node33, node41);
  418.     triangle.addEdge(node33, node42);
  419.     triangle.addEdge(node34, node42);
  420.     triangle.addEdge(node34, node43);
  421.     triangle.addEdge(node35, node43);
  422.     triangle.addEdge(node35, node44);
  423.  
  424.     triangle.addEdge(node36, node45);
  425.     triangle.addEdge(node36, node46);
  426.     triangle.addEdge(node37, node46);
  427.     triangle.addEdge(node37, node47);
  428.     triangle.addEdge(node38, node47);
  429.     triangle.addEdge(node38, node48);
  430.     triangle.addEdge(node39, node48);
  431.     triangle.addEdge(node39, node49);
  432.     triangle.addEdge(node40, node49);
  433.     triangle.addEdge(node40, node50);
  434.     triangle.addEdge(node41, node50);
  435.     triangle.addEdge(node41, node51);
  436.     triangle.addEdge(node42, node51);
  437.     triangle.addEdge(node42, node52);
  438.     triangle.addEdge(node43, node52);
  439.     triangle.addEdge(node43, node53);
  440.     triangle.addEdge(node44, node53);
  441.     triangle.addEdge(node44, node54);
  442.  
  443.     triangle.addEdge(node45, node55);
  444.     triangle.addEdge(node45, node56);
  445.     triangle.addEdge(node46, node56);
  446.     triangle.addEdge(node46, node57);
  447.     triangle.addEdge(node47, node57);
  448.     triangle.addEdge(node47, node58);
  449.     triangle.addEdge(node48, node58);
  450.     triangle.addEdge(node48, node59);
  451.     triangle.addEdge(node49, node59);
  452.     triangle.addEdge(node49, node60);
  453.     triangle.addEdge(node50, node60);
  454.     triangle.addEdge(node50, node61);
  455.     triangle.addEdge(node51, node61);
  456.     triangle.addEdge(node51, node62);
  457.     triangle.addEdge(node52, node62);
  458.     triangle.addEdge(node52, node63);
  459.     triangle.addEdge(node53, node63);
  460.     triangle.addEdge(node53, node64);
  461.     triangle.addEdge(node54, node64);
  462.     triangle.addEdge(node54, node65);
  463.  
  464.     triangle.addEdge(node55, node66);
  465.     triangle.addEdge(node55, node67);
  466.     triangle.addEdge(node56, node67);
  467.     triangle.addEdge(node56, node68);
  468.     triangle.addEdge(node57, node68);
  469.     triangle.addEdge(node57, node69);
  470.     triangle.addEdge(node58, node69);
  471.     triangle.addEdge(node58, node70);
  472.     triangle.addEdge(node59, node70);
  473.     triangle.addEdge(node59, node71);
  474.     triangle.addEdge(node60, node71);
  475.     triangle.addEdge(node60, node72);
  476.     triangle.addEdge(node61, node72);
  477.     triangle.addEdge(node61, node73);
  478.     triangle.addEdge(node62, node73);
  479.     triangle.addEdge(node62, node74);
  480.     triangle.addEdge(node63, node74);
  481.     triangle.addEdge(node63, node75);
  482.     triangle.addEdge(node64, node75);
  483.     triangle.addEdge(node64, node76);
  484.     triangle.addEdge(node65, node76);
  485.     triangle.addEdge(node65, node77);
  486.  
  487.     triangle.addEdge(node66, node78);
  488.     triangle.addEdge(node66, node79);
  489.     triangle.addEdge(node67, node79);
  490.     triangle.addEdge(node67, node80);
  491.     triangle.addEdge(node68, node80);
  492.     triangle.addEdge(node68, node81);
  493.     triangle.addEdge(node69, node81);
  494.     triangle.addEdge(node69, node82);
  495.     triangle.addEdge(node70, node82);
  496.     triangle.addEdge(node70, node83);
  497.     triangle.addEdge(node71, node83);
  498.     triangle.addEdge(node71, node84);
  499.     triangle.addEdge(node72, node84);
  500.     triangle.addEdge(node72, node85);
  501.     triangle.addEdge(node73, node85);
  502.     triangle.addEdge(node73, node86);
  503.     triangle.addEdge(node74, node86);
  504.     triangle.addEdge(node74, node87);
  505.     triangle.addEdge(node75, node87);
  506.     triangle.addEdge(node75, node88);
  507.     triangle.addEdge(node76, node88);
  508.     triangle.addEdge(node76, node89);
  509.     triangle.addEdge(node77, node89);
  510.     triangle.addEdge(node77, node90);
  511.  
  512.     triangle.addEdge(node78, node91);
  513.     triangle.addEdge(node78, node92);
  514.     triangle.addEdge(node79, node92);
  515.     triangle.addEdge(node79, node93);
  516.     triangle.addEdge(node80, node93);
  517.     triangle.addEdge(node80, node94);
  518.     triangle.addEdge(node81, node94);
  519.     triangle.addEdge(node81, node95);
  520.     triangle.addEdge(node82, node95);
  521.     triangle.addEdge(node82, node96);
  522.     triangle.addEdge(node83, node96);
  523.     triangle.addEdge(node83, node97);
  524.     triangle.addEdge(node84, node97);
  525.     triangle.addEdge(node84, node98);
  526.     triangle.addEdge(node85, node98);
  527.     triangle.addEdge(node85, node99);
  528.     triangle.addEdge(node86, node99);
  529.     triangle.addEdge(node86, node100);
  530.     triangle.addEdge(node87, node100);
  531.     triangle.addEdge(node87, node101);
  532.     triangle.addEdge(node88, node101);
  533.     triangle.addEdge(node88, node102);
  534.     triangle.addEdge(node89, node102);
  535.     triangle.addEdge(node89, node103);
  536.     triangle.addEdge(node90, node103);
  537.     triangle.addEdge(node90, node104);
  538.  
  539.     triangle.addEdge(node91, node105);
  540.     triangle.addEdge(node91, node106);
  541.     triangle.addEdge(node92, node106);
  542.     triangle.addEdge(node92, node107);
  543.     triangle.addEdge(node93, node107);
  544.     triangle.addEdge(node93, node108);
  545.     triangle.addEdge(node94, node108);
  546.     triangle.addEdge(node94, node109);
  547.     triangle.addEdge(node95, node109);
  548.     triangle.addEdge(node95, node110);
  549.     triangle.addEdge(node96, node110);
  550.     triangle.addEdge(node96, node111);
  551.     triangle.addEdge(node97, node111);
  552.     triangle.addEdge(node97, node112);
  553.     triangle.addEdge(node98, node112);
  554.     triangle.addEdge(node98, node113);
  555.     triangle.addEdge(node99, node113);
  556.     triangle.addEdge(node99, node114);
  557.     triangle.addEdge(node100, node114);
  558.     triangle.addEdge(node100, node115);
  559.     triangle.addEdge(node101, node115);
  560.     triangle.addEdge(node101, node116);
  561.     triangle.addEdge(node102, node116);
  562.     triangle.addEdge(node102, node117);
  563.     triangle.addEdge(node103, node117);
  564.     triangle.addEdge(node103, node118);
  565.     triangle.addEdge(node104, node118);
  566.     triangle.addEdge(node104, node119);
  567.  
  568.  
  569.  
  570.  
  571.  
  572.  
  573.     //finalValue = triangle.DFS(node0);
  574.  
  575.     //cout << "Final DFS Total: " << finalValue << endl;
  576.  
  577.  
  578.     cout << endl;
  579.     finalValue = triangle.BFS(node0);
  580.     cout << "Final BFS total: " << finalValue;
  581.     cout << endl;
  582.  
  583.  
  584.  
  585.     cout << endl;
  586.     system("Pause");
  587.     return 0;
  588. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!