daily pastebin goal
7%
SHARE
TWEET

Untitled

a guest Dec 25th, 2018 68 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include<queue>
  3. #include<vector>
  4. #include<fstream>
  5. using namespace std;
  6. int main(){
  7.     ifstream in;
  8.     ofstream ou;
  9.     in.open("input.txt");
  10.     ou.open("output.txt");
  11.     long long nodi,archi,nodoiniziale,nododaraggiungere;
  12.     priority_queue<pair<long long,long long>,vector<pair<long long,long long>>,greater<pair<long long,long long>>>q;
  13.     in>>nodi;
  14.     in>>archi;
  15.     in>>nodoiniziale;
  16.     in>>nododaraggiungere;
  17.     nodoiniziale--;
  18.     nododaraggiungere--;
  19.     long long a,b,c;
  20.     vector<pair<long long,long long>> v[nodi];
  21.     for(int i=0;i<archi;i++){
  22.         in>>a;
  23.         in>>b;
  24.         in>>c;
  25.         a--;
  26.         b--;
  27.         v[a].push_back({b,c});
  28.     }
  29.     long long visitato[nodi];
  30.     long long distanze[nodi];
  31.     for(int i=0;i<nodi;i++){
  32.         distanze[i]=1e9;
  33.         visitato[i]=0;
  34.     }
  35.     distanze[nodoiniziale]=0;
  36.     q.push({0,nodoiniziale});
  37.     long long corrente;
  38.     while(!q.empty()){
  39.         corrente=q.top().second;
  40.         q.pop();
  41.         if(visitato[corrente]==0){
  42.             visitato[corrente]=1;
  43.             for(auto y:v[corrente]){
  44.                 if(distanze[corrente]+y.second<distanze[y.first]){
  45.                     distanze[y.first]=distanze[corrente]+y.second;
  46.                     q.push({distanze[y.first],y.first});
  47.                 }
  48.             }
  49.         }
  50.     }
  51.     ou<<distanze[nododaraggiungere];
  52.     return 0;
  53. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top