Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <queue>
- #include <utility>
- using namespace std;
- using pii = pair<int,int>;
- int main(){
- int n;
- cin >> n;
- int w[n+1];
- for(int i=1;i<=n;++i){
- cin >> w[i];
- }
- int m;
- cin >> m;
- int u1,v1;
- vector <int> g[n+1];
- for(int i=0;i<m;++i){
- cin >> u1 >> v1;
- g[u1].push_back(v1);
- g[v1].push_back(u1);
- }
- vector<int> dist(n+1,2e9);
- vector<bool> visited(n+1,false);
- priority_queue<pii, vector<pii>, greater<pii>> q;
- dist[1]=0;
- q.push({dist[1],1});
- int sum = 0;
- while(!q.empty()){
- int u=q.top().second , d=q.top().first;
- q.pop();
- if(visited[u]){
- continue;
- }
- visited[u]=true;
- sum+=dist[u];
- for(auto c:g[u]){
- int z=w[u]+w[c];
- if(!visited[c]&&z<dist[c]){
- dist[c]=z;
- q.push({dist[c],c});
- }
- }
- }
- cout << sum;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement