Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <iostream>
- #include <queue>
- #include <utility>
- #include <vector>
- using namespace std;
- #define DISTANCE_INITIALIZATION_VALUE -1
- void add_edge_directed(vector<vector<pair<long long, long long>>> &G,
- long long u, long long v, long long weight) {
- G.at(u).push_back(make_pair(v, weight));
- // G.at(v).push_back(make_pair(u, weight));
- }
- class Compare {
- public:
- // Ringraziamo l'umile dipendente cicciottello
- // per aver scoperto la necessitá di una inspiegabile parentesi tonda
- bool operator()(pair<long long, long long> &lhs,
- pair<long long, long long> &rhs) {
- return lhs.second > rhs.second;
- }
- };
- int main() {
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- long long V, E;
- cin >> V >> E;
- vector<vector<pair<long long, long long>>> G(V, vector<pair<long long, long long>>());
- long long source, destination;
- cin >> source >> destination;
- // Per gli indici che partono da 1
- // source--;
- // destination--;
- for (long long edge = 0; edge < E; edge++) {
- long long u, v, w;
- cin >> u >> v >> w;
- // Per gli indici che partono da 1
- // u--;
- // v--;
- add_edge_directed(G, u, v, w);
- }
- // Shortest path
- priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, Compare> queue;
- queue.push(make_pair(source, 0));
- vector<bool> visited(V, false);
- vector<long long> distances(V, DISTANCE_INITIALIZATION_VALUE);
- while (!queue.empty()) {
- pair<long long, long long> curr = queue.top();
- queue.pop();
- if (!visited.at(curr.first)) {
- visited.at(curr.first) = true;
- distances.at(curr.first) = curr.second;
- for (pair<long long, long long> neighbour : G.at(curr.first)) {
- if (!visited.at(neighbour.first)) {
- queue.push(
- make_pair(neighbour.first, curr.second + neighbour.second));
- }
- }
- }
- }
- cout << distances.at(destination);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement