# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
983894 | 2024-05-16T07:47:58 Z | Rafiullah | Cyberland (APIO23_cyberland) | C++17 | 0 ms | 0 KB |
#include<bits/stdc++.h> using namespace std; #define int long long #define ll long long void solve(){ int n ,m , k,h;cin>>n>>m>>k>>h; map<int,vector<int>> graph; map<pair<int,int>,int> weight; int A[n]; int dist[n]; for(int i = 0 ;i <n ;i ++){ dist[i] = 1e9; cin>>A[i]; } for(int i = 0 ;i<m ;i ++){ int a ,b,c;cin>>a>>b>>c; weight[{min(a,b),max(a,b)}] = c; graph[a].push_back(b); graph[b].push_back(a); } priority_queue<pair<int,int>> pq; dist[0]=0; pq.push({0,0}); while(pq.size()>0){ int node = pq.top().second; pq.pop(); // cout<<graph[node].size()<<endl; for(int child:graph[node]){ int W = weight[{min(node,child),max(node,child)}]; // cout<<node<<" "<<child<<" "<<W<<endl; if(dist[node]+W<dist[child]){ dist[child] = dist[node]+W; pq.push({-dist[child],child}); } } } if(dist[h] == 1e9)dist[h] = -1; cout<<dist[h]<<endl; } signed main(){ int t = 1; cin >> t; while (t--){ solve(); } }