Submission #919166

#TimeUsernameProblemLanguageResultExecution timeMemory
919166vjudge1Inspections (NOI23_inspections)C++17
0 / 100
1 ms348 KiB
/****************************************************************************** Online C++ Compiler. Code, Compile, Run and Debug C++ program online. Write your code in this editor and press "Run" button to compile and execute it. *******************************************************************************/ #include <bits/stdc++.h> using namespace std; const long int base = 1e18; int main() { int n,m; cin>>n>>m; long long int a[n+1]; long long int h[n+1]; for(int i =1;i<=n;i++){ cin>>a[i]; h[i]=base; } vector<int> arr[n+1]; for(int i =0;i<m;i++){ int a,b; cin>>a>>b; arr[a].push_back(b); arr[b].push_back(a); } priority_queue<pair<long long int,int> , vector<pair<long long int,int>>, greater<pair<long long int,int>> > q; h[1]=0; q.push({0,1}); while(!q.empty()){ int u = q.top().second; long long int d = q.top().first; q.pop(); if(d!=h[u])continue; for(int v : arr[u]){ long long int ans = d; if(a[v]==a[u]){ ans++; }else{ ans+=abs(a[v]-a[u]); } if(ans>=h[v])continue; h[v]=ans; q.push({ans,v}); } } cout<<h[n]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...