HA31_Paths(9)

coloriot

Nov 15th, 2024

Never

Add comment

Not a member of Pastebin yet? Sign Up, it unlocks many cool features!

C++ 1.98 KB | None | 0 0

raw download clone embed print report

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int INF = 1000000000;
class Edge {
public:
int to;
int weight;
Edge(int t, int w) {
to = t;
weight = w;
}
};
class Graph {
private:
int N;
vector<vector<Edge> > adj;
vector<int> dist;
vector<bool> used;
public:
Graph(int n) {
N = n;
adj.resize(N);
dist.resize(N, INF);
used.resize(N, false);
}
void add_edge(int from, int to, int weight) {
adj[from].push_back(Edge(to, weight));
}
int dijkstra(int start_v, int end_v) {
dist[start_v] = 0;
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
pq.push(make_pair(0, start_v));
while (!pq.empty()) {
pair<int, int> p = pq.top();
pq.pop();
int v = p.second;
int d = p.first;
if (used[v]) {
continue;
}
used[v] = true;
if (v == end_v) {
return dist[end_v];
}
for (size_t i = 0; i < adj[v].size(); ++i) {
int to = adj[v][i].to;
int weight = adj[v][i].weight;
if (dist[v] + weight < dist[to]) {
dist[to] = dist[v] + weight;
pq.push(make_pair(dist[to], to));
}
}
}
if (dist[end_v] == INF) {
return -1;
} else {
return dist[end_v];
}
}
};
int main() {
int N, M;
cin >> N >> M;
int S, F;
cin >> S >> F;
S--;
F--;
Graph graph(N);
for (int i = 0; i < M; ++i) {
int A, B, T;
cin >> A >> B >> T;
A--;
B--;
graph.add_edge(A, B, T);
}
int result = graph.dijkstra(S, F);
cout << result << endl;
return 0;
}

Add Comment

Please, Sign In to add comment