Untitled
unknown
c_cpp
4 years ago
1.4 kB
5
Indexable
#include <iostream> #include <cmath> #include <algorithm> #include <vector> #include <queue> using namespace std; struct node { int idx; int weight; node(){ // empty constructor } node(int a, int b) { // parameter constructor idx = a; weight = b; } bool operator < (const node &tmp) const { return weight > tmp.weight; } }; int main() { int n, m; // broj na teminja i broj na rebra cin >> n >> m; vector<pair<int, int> > graph[n + 1]; for(int i = 0; i < m; i++) { int a, b, c; cin >> a >> b >> c; graph[a].push_back(make_pair(b, c)); graph[b].push_back(make_pair(a, c)); } int S, E; cin >> S >> E; vector<bool> visited(n + 1, false); vector<int> dist(n + 1, 2e9); priority_queue<node> pq; pq.push(node(S, 0)); dist[S] = 0; while(!pq.empty()) { node c = pq.top(); pq.pop(); visited[c.idx] = true; for(int i = 0; i < graph[c.idx].size(); i++) { int neighbour = graph[c.idx][i].first; int d = graph[c.idx][i].second; if(!visited[neighbour] and c.weight + d < dist[neighbour]) { dist[neighbour] = c.weight + d; pq.push(node(neighbour, dist[neighbour])); } } } cout << dist[E] << endl; return 0; }
Editor is loading...