# Untitled

unknown
c_cpp
3 years ago
1.4 kB
1
Indexable
Never
```#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;
}

```