제출 #951281

#제출 시각아이디문제언어결과실행 시간메모리
951281NourWaelRelay Marathon (NOI20_relaymarathon)C++17
0 / 100
1 ms520 KiB
#include <bits/stdc++.h> #define int long long using namespace std; int const mxN = 1e3+5; vector<pair<int,int>> adj[mxN]; vector<int> spe; bool is[mxN], vis[mxN]; int dist[mxN][mxN], cur[mxN], come[mxN]; int n; vector<pair<int,int>> lis[mxN]; int solve () { memset(vis,0,sizeof vis); for(int j=1; j<=n; j++) cur[j] = 1e18; priority_queue<pair<int,pair<int,int>>> q; for(auto it:spe) { q.push({0,{it, it}}); cur[it] = 0; come[it] = it;} int ans = 1e18; while(q.size()) { int node = q.top().second.first, from = q.top().second.second, d = -(q.top().first); q.pop(); if(vis[node]) continue; vis[node] = 1; for(auto it:adj[node]) { if(come[it.first]!=from) ans = min (ans, d+it.second+cur[it.first]); if(cur[it.first]<=d+it.second) continue; cur[it.first] = d+it.second; come[it.first] = from; q.push({-(d+it.second), {it.first,from}}); } } return ans; } signed main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); int m,k; cin>>n>>m>>k; for(int i=0; i<m; i++) { int x,y,c; cin>>x>>y>>c; adj[x].push_back({y,c}), adj[y].push_back({x,c}); } for(int i=0; i<k; i++) { int x; cin>>x; is[x] = 1; if(x!=1 && x!=2) spe.push_back(x); } cout<<solve()+1; return 0; } /* 7 6 4 1 2 1 7 3 1 3 4 2 4 5 3 5 6 5 6 3 4 1 2 5 7 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...