이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |