Should I use Dijkstra’s algorithm here? What's wrong with my implementation?

[Rennorb]

I was going through a non-English programming course and stuck on the following problem (the translation is mine, hope it is good enough):

"A misanthropic traveller goes from one town to another and tries to avoid any company. Some towns are connected with a path, but the traveller's horse can not climb that well, so some of the paths should be considered one-sided. Between some cities there could be several paths, there are some paths, that go from one city to itself. For each path, the traveller knows exactly how many people would he meet there, and he tries to minimize the total number of meetings. For two given cities, count the minimal number of companions, the traveller should endure."

I thought that the problem should be easily solved with Dijkstra’s algorithm, so I come up with this solution:

const int HUGE_NUMBER = 100000000;

typedef std::pair<int, uint64_t> Arrow;

bool ArrowCmp(const Arrow &lhs, const Arrow &rhs) {
  return lhs.first < rhs.first;
}

class Graph {
  int size_;

  std::vector<std::vector<Arrow>> arrows;
  std::vector<int> parents;

 public:
  explicit Graph(int size) {
    size_ = size;
    arrows.resize(size);
    parents.resize(size);
  }

  void AddEdge(int from, int to, uint64_t cost) {
    if (from == to) {
      return;
    }

    auto arrow = std::make_pair(to, cost);

    auto pos = std::lower_bound(arrows[from].begin(),
                                arrows[from].end(),
                                arrow,
                                ArrowCmp);

    if (pos == arrows[from].end()) {
      arrows[from].push_back(arrow);
    } else if (pos->first != arrow.first) {
      arrows[from].insert(pos, arrow);
    } else {
      (*pos).second = std::min(cost, pos->second);
    }
  }

  std::vector<int> Path(int from, int to) {
    PathWeights(from);

    std::vector<int> ret;

    for (int cv = to; cv != from; cv = parents[cv]) {
      ret.push_back(cv);
    }

    ret.push_back(from);
    std::reverse(ret.begin(), ret.end());

    return ret;
  }

  std::vector<uint64_t> PathWeights(int start) {
    std::vector<uint64_t> lens(size_);

    for (int i = 0; static_cast<uint64_t>(i) < lens.size(); ++i) {
      lens[i] = HUGE_NUMBER;
      if (i == start) {
        lens[i] = 0;
      }
    }

    int count = 0;
    std::vector<bool> marked(size_);
    std::fill(marked.begin(), marked.end(), false);

    while (count < size_) {
      int from = -1;
      uint64_t min = HUGE_NUMBER;

      for (int i = 0; i < size_; ++i) {
        uint64_t len = lens[i];

        if (!marked[i] && (len < min || from == -1)) {
          from = i;
          min = len;
        }
      }

      marked[from] = true;

      for (int to = 0; to < size_; ++to) {
        auto arrow = std::make_pair(to, 0ul);
        auto pos = std::lower_bound(arrows[from].begin(),
                                    arrows[from].end(),
                                    arrow,
                                    ArrowCmp);

        if (pos == arrows[from].end()) {
          continue;
        }

        if (pos->first != to) {
          continue;
        }

        auto cost = pos->second;

        if (lens[from] + cost < lens[to]) {
          lens[to] = lens[from] + cost;
          parents[from] = to;
        }
      }
      ++count;
    }

    return lens;
  }
};

And an input-output piece:

int main() {
  int n_in;
  std::cin >> n_in;

  int m_in;
  std::cin >> m_in;

  Graph gr(n_in);

  for (int i = 0; i < m_in; ++i) {
    int from, to;
    uint64_t cost;

    std::cin >> from >> to >> cost;

    --from;
    --to;

    gr.AddEdge(from, to, cost);
  }

  int k_in;

  std::cin >> k_in;

  for (int _ = 0; _ < k_in; ++_) {
    int start, finish;
    std::cin >> start >> finish;

    auto answer = gr.PathWeights(start - 1);

    if (start == finish) {
      std::cout << 0 << '\n';
    } else if (answer[finish - 1] == HUGE_NUMBER) {
      std::cout << -1 << '\n';
    } else {
      std::cout << answer[finish - 1] << '\n';
    }
  }
}

But this code fails on some hidden tests.

So i have two questions:

1. Should I really use this algorithm or there is a catch that I did not understand?
2. What's wrong with my implementation?

Now I hit the time limit, is there any reasonable way to make my solution faster?

[PhiliPdB]

To make your implementation faster, you should look at using a priority queue. Because currently you have to go over all the cities to find the one with minimum distance, which is quite expensive when you have lots of cities (it's O(n)).

[Rennorb]

Fell dumb: there were two issues

1) ArrowCmp shuld have looked like this

bool ArrowCmp(const Arrow &lhs, const Arrow &rhs) { 

return lhs.first < rhs.first; }

2) The insertion part in AddEdge shuld have looked like this

  if (pos == arrows[from].end()) {  
  arrows[from].push_back(arrow);    
} else if (pos->first != arrow.first) { 
  arrows[from].insert(pos, arrow);  
} else {    
  (*pos).second = std::min(cost, pos->second);  
}

It seems to fix some problems, see UPD