pastebin

Paste Search Dynamic
Recent pastes
dijstra
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3. #define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  4. using namespace std;
  5.  
  6. long long dist1[100005],dist2[100005];
  7. long long vis[100005];
  8.  
  9. void dijstra(long long src,vector<pair<long long,long long>>graph[],long long dist[]){
  10.        
  11.         vis[src]=true;
  12.         for(long long i=0;i<100005;i++){
  13.                 dist[i]=1e18;
  14.         }
  15.         priority_queue<pair<long long,long long>,vector<pair<long long,long long>>,greater<pair<long long,long long>>>pq;
  16.         dist[src]=0;
  17.         for(long long i=1;i<=100005;i++){
  18.                 vis[i]=false;
  19.         }
  20.        
  21.         pq.push({0,src});
  22.        
  23.         while(!pq.empty()){
  24.                
  25.                 long long node=pq.top().second;
  26.                 long long dista=pq.top().first;
  27.                 pq.pop();
  28.                 if(vis[node]){
  29.                         continue;
  30.                 }
  31.                 vis[node]=true;
  32.                 for(auto it:graph[node]){
  33.                         if(!vis[it.first]){
  34.                                 if(dist[it.first]>dist[node]+it.second){
  35.                                         dist[it.first]=dist[node]+it.second;
  36.                                         pq.push({dist[it.first],it.first});
  37.                                 }
  38.                         }
  39.                 }
  40.         }
  41. }
  42.  
  43. int main() {
  44.        
  45.         fast;
  46.         int n,m;
  47.         cin>>n>>m;
  48.        
  49.         vector<pair<long long,long long>>graph1[n+1];
  50.         vector<pair<long long,long long>>graph2[n+1];
  51.         vector<tuple<long long,long long,long long>>edges;
  52.        
  53.         for(long long i=0;i<m;i++){
  54.                 long long u,v,wt;
  55.                 cin>>u>>v>>wt;
  56.                 graph1[u].push_back({v,wt});
  57.                 graph2[v].push_back({u,wt});
  58.                 edges.push_back({u,v,wt});
  59.         }
  60.                
  61.                 dijstra(1,graph1,dist1);
  62.                 dijstra(n,graph2,dist2);
  63.                
  64.                 long long ans=1e18;
  65.                
  66.                 for(auto [u,v,w]:edges){
  67.                         ans=min(ans,dist1[u]+dist2[v]+w/2);
  68.                 }
  69.                
  70.                 cout<<ans<<endl;
  71.                
  72.        
  73.         return 0;
  74. }
Parsed in 0.017 seconds