fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <utility>
  5. #include <limits>
  6. using namespace std;
  7.  
  8. struct Node;
  9.  
  10. typedef pair<int, Node*> Edge; // weight and target node
  11.  
  12. struct Node
  13. {
  14.     bool isFlooded;
  15.     bool dijkstraMark;
  16.     int value;
  17.  
  18.     typedef vector<Edge> EdgeList;
  19.     EdgeList adjacentNodes;
  20.  
  21.     Node():
  22.         isFlooded( true ),
  23.         dijkstraMark( false ),
  24.         value( numeric_limits<int>::max() )
  25.     {}
  26. };
  27.  
  28. typedef vector<Node> AdjacencyList;
  29.  
  30. struct NodeComparer
  31. {
  32.     bool operator()(const Node& n1, const Node& n2)
  33.     {
  34.         return (n1.value) >= (n2.value);
  35.     }
  36. };
  37.  
  38. void solve( AdjacencyList& graph, Node* currentNode )
  39. {
  40.     currentNode->dijkstraMark = true;
  41.  
  42.     int adjacentSize = currentNode->adjacentNodes.size();
  43.     for( int i=0; i < adjacentSize; i++ )
  44.     {
  45.         Edge& edge = currentNode->adjacentNodes[i];
  46.         if(( currentNode->isFlooded &&
  47.              (currentNode->value + edge.first ) > 20 )
  48.             ||
  49.             ( edge.first > 20 ) )
  50.         {
  51.             edge.second->value = numeric_limits<int>::max();
  52.         }
  53.         // the node is valid
  54.         else if(( currentNode->value + edge.first ) < edge.second->value )
  55.         {
  56.             edge.second->value = currentNode->value + edge.first;
  57.         }
  58.     }
  59.  
  60.     int pos = -1;
  61.     int minValue = numeric_limits<int>::max();
  62.     for( size_t i=0; i < graph.size(); i++ )
  63.     {
  64.         if( !graph[i].dijkstraMark && graph[i].value <= minValue )
  65.         {
  66.             pos = i;
  67.             minValue = graph[i].value;
  68.         }
  69.     }
  70.  
  71.     if( pos != -1 )
  72.     {
  73.         solve( graph, &graph[pos] );
  74.     }
  75. }
  76.  
  77. int main()
  78. {
  79.     istream& in = cin;
  80.  
  81.     int nodes, edges, goalNode, emptyNodes;
  82.     in >> nodes >> edges >> goalNode >> emptyNodes;
  83.  
  84.     AdjacencyList graph( nodes );
  85.  
  86.     for( int i=0; i < emptyNodes; i++ )
  87.     {
  88.         int nodeId;
  89.         in >> nodeId;
  90.         graph[nodeId-1].isFlooded = false;
  91.     }
  92.  
  93.     for( int i=0; i < edges; i++ )
  94.     {
  95.         int firstEdge, secondEdge, weight;
  96.         in >> firstEdge >> secondEdge >> weight;
  97.  
  98.         graph[firstEdge-1].adjacentNodes.push_back( make_pair( weight, &graph[secondEdge-1] ));
  99.         graph[secondEdge-1].adjacentNodes.push_back( make_pair( weight, &graph[firstEdge-1] ));
  100.     }
  101.  
  102.     graph[0].value = 0;
  103.  
  104.     solve( graph, &graph[0] );
  105.     ostream& out = cout;
  106.     if( graph[goalNode-1].value == numeric_limits<int>::max() )
  107.     {
  108.         graph[goalNode-1].value = -1;
  109.     }
  110.     out << graph[goalNode-1].value;
  111.  
  112.     return 0;
  113. }
Success #stdin #stdout 0.02s 2860KB
comments (?)
stdin
copy 
3 3 2 2
2 3
1 2 22
1 3 15
2 3 14
stdout
copy 
29
https://ideone.com/E4koS
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
secret

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!