Untitled

 avatar
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...