daily pastebin goal
11%
SHARE
TWEET

Untitled

a guest Dec 24th, 2018 73 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.     int nodi,archi,nodoiniziale,nododaraggiungere;
  12.     in>>nodi;
  13.     vector<pair<int,int>> v[nodi];
  14.     in>>archi;
  15.     in>>nodoiniziale;
  16.     nodoiniziale--;
  17.     in>>nododaraggiungere;
  18.     nododaraggiungere--;
  19.     int a,b,c;
  20.     for(int i=0;i<archi;i++){
  21.         in>>a;
  22.         in>>b;
  23.         in>>c;
  24.         a--;
  25.         b--;
  26.         v[a].push_back({b,c});
  27.         v[b].push_back({a,c});
  28.     }
  29.     priority_queue<pair<int,int>> q;
  30.     int visitato[nodi];
  31.     int distanze[nodi];
  32.     for(int i=0;i<nodi;i++){
  33.         visitato[i]=0;
  34.         distanze[i]=1e9;
  35.     }
  36.     distanze[nodoiniziale]=0;
  37.     q.push({nodoiniziale,0});
  38.     int corrente;
  39.     while (q.size()!=0||corrente!=nododaraggiungere){
  40.         corrente= q.top().first;
  41.         q.pop();
  42.         if (visitato[corrente]==0){
  43.             visitato[corrente] = 1;
  44.             for (auto w : v[corrente]) {
  45.                 if (distanze[corrente]+w.second < distanze[w.first]) {
  46.                     distanze[w.first] = distanze[corrente]+w.second;
  47.                     q.push({w.first,-distanze[w.first]});
  48.                 }
  49.             }
  50.         }
  51.     }
  52.     ou<<distanze[nododaraggiungere];
  53.     return 0;
  54. }
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