# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
983871 | 2024-05-16T07:35:00 Z | Rafiullah | 사이버랜드 (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 X[n]; int Y[n]; int C[n]; for(int i = 0 ;i <m ;i ++){ cin>>X[i]; } for(int i = 0 ;i <m ; i++){ cin>>Y[i]; } for(int i= 0 ; i<m ;i ++){ cin>>C[i]; } 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 = X[i]; int b = Y[i]; int c = C[i]; 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(); for(int child:graph[node]){ int W = weight[{min(node,child),max(node,child)}]; if(dist[node]+W<dist[child]){ dist[child] = dist[node]+W; pq.push({-dist[child],child}); } } } cout<<dist[h]<<endl; } signed main(){ int t = 1; cin >> t; while (t--){ solve(); } }