Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <queue>
- #include <vector>
- using namespace std;
- /*
- 0: (1, 2)
- 1:
- 2:
- 3:
- 4:
- **/
- struct node {
- int index, shortest_cost;
- node(int i, int s) {
- index = i;
- shortest_cost = s;
- }
- bool operator < (const node &tmp) const {
- return shortest_cost > tmp.shortest_cost;
- }
- };
- int main()
- {
- int n, m; // broj na teminja, broj na rebra
- cin >> n >> m;
- vector<pair<int, int> > graph[n + 5];
- for(int i = 0; i < m; i++) {
- int a, b, c; // temeto A e povrzano so temeto B i odaleceni se so 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;
- // od kade sakam do kade sakam da najdam najkratok pat
- priority_queue<node> pq;
- pq.push(node(S, 0));
- vector<bool> visited(n + 1, false);
- while(!pq.empty()) {
- node current = pq.top(); // kazi mi koj e najmal sosed
- pq.pop();
- visited[current.index] = true;
- if(current.index == E) {
- cout << current.shortest_cost << endl; // ova e najkratkiot pat
- break;
- }
- for(int i = 0; i < graph[current.index].size(); i++) {
- int sosed = graph[current.index][i].first;
- int pat = graph[current.index][i].second;
- if(!visited[sosed]) {
- pq.push(node(sosed, current.shortest_cost + pat));
- }
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement