Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include<queue>
- #include<vector>
- #include<fstream>
- using namespace std;
- int main(){
- ifstream in;
- ofstream ou;
- in.open("input.txt");
- ou.open("output.txt");
- long long nodi,archi,nodoiniziale,nododaraggiungere;
- priority_queue<pair<long long,long long>,vector<pair<long long,long long>>,greater<pair<long long,long long>>>q;
- in>>nodi;
- in>>archi;
- in>>nodoiniziale;
- in>>nododaraggiungere;
- nodoiniziale--;
- nododaraggiungere--;
- long long a,b,c;
- vector<pair<long long,long long>> v[nodi];
- for(int i=0;i<archi;i++){
- in>>a;
- in>>b;
- in>>c;
- a--;
- b--;
- v[a].push_back({b,c});
- }
- long long visitato[nodi];
- long long distanze[nodi];
- for(int i=0;i<nodi;i++){
- distanze[i]=1e9;
- visitato[i]=0;
- }
- distanze[nodoiniziale]=0;
- q.push({0,nodoiniziale});
- long long corrente;
- while(!q.empty()){
- corrente=q.top().second;
- q.pop();
- if(visitato[corrente]==0){
- visitato[corrente]=1;
- for(auto y:v[corrente]){
- if(distanze[corrente]+y.second<distanze[y.first]){
- distanze[y.first]=distanze[corrente]+y.second;
- q.push({distanze[y.first],y.first});
- }
- }
- }
- }
- ou<<distanze[nododaraggiungere];
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement