You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
74 lines
1.8 KiB
C++
74 lines
1.8 KiB
C++
#include <vector>
|
|
#include <queue>
|
|
#include <set>
|
|
#include <climits>
|
|
#include <iostream>
|
|
using namespace std;
|
|
|
|
typedef pair<int, int> pii;
|
|
typedef vector<vector<pii> > Graph;
|
|
|
|
void dijkstra(Graph &g, int s, vector<int> &prio, vector<int> &pred) {
|
|
int n = g.size();
|
|
prio.assign(n, INT_MAX);
|
|
prio[s] = 0;
|
|
pred.assign(n, -1);
|
|
priority_queue<pii, vector<pii> , greater<pii> > q;
|
|
q.push(make_pair(prio[s], s));
|
|
|
|
while (!q.empty()) {
|
|
int d = q.top().first;
|
|
int u = q.top().second;
|
|
q.pop();
|
|
if (d != prio[u])
|
|
continue;
|
|
for (int i = 0; i < (int) g[u].size(); i++) {
|
|
int v = g[u][i].first;
|
|
int nprio = prio[u] + g[u][i].second;
|
|
if (prio[v] > nprio) {
|
|
prio[v] = nprio;
|
|
pred[v] = u;
|
|
q.push(make_pair(nprio, v));
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
void dijkstra2(Graph &g, int s, vector<int> &prio, vector<int> &pred) {
|
|
int n = g.size();
|
|
prio.assign(n, INT_MAX);
|
|
prio[s] = 0;
|
|
pred.assign(n, -1);
|
|
set<pii> q;
|
|
q.insert(make_pair(prio[s], s));
|
|
|
|
while (!q.empty()) {
|
|
int u = q.begin()->second;
|
|
q.erase(q.begin());
|
|
for (int i = 0; i < (int) g[u].size(); ++i) {
|
|
int v = g[u][i].first;
|
|
int nprio = prio[u] + g[u][i].second;
|
|
if (prio[v] > nprio) {
|
|
q.erase(make_pair(prio[v], v));
|
|
prio[v] = nprio;
|
|
pred[v] = u;
|
|
q.insert(make_pair(prio[v], v));
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
int main() {
|
|
Graph g(3);
|
|
g[0].push_back(make_pair(1, 10));
|
|
g[1].push_back(make_pair(2, -5));
|
|
g[0].push_back(make_pair(2, 8));
|
|
|
|
vector<int> prio;
|
|
vector<int> pred;
|
|
dijkstra(g, 0, prio, pred);
|
|
|
|
for (int i = 0; i < prio.size(); i++)
|
|
cout << prio[i] << endl;
|
|
}
|