| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 448093 | training4usaco | 악어의 지하 도시 (IOI11_crocodile) | C++11 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define INF 1000000009
struct Edge {
int a, b, weight;
Edge(int _a, int _b) : a(_a), b(_b) {
}
};
#define mp make_pair
#define fi first
#define se second
int trave_plan(int n, int m, vector<vector<int>> edges, vector<int> weights, int k, vector<int> exits) {
// cout << n << " " << m << " " << k << endl;
vector<Edge> edges;
vector<vector<pair<int, int>>> adj(n);
// cout << "edges: " << endl;
for(int i = 0; i < m; ++i) {
// cout << edges[i].a << " " << edges[i].b << " " << edges[i].weight << endl;;
adj[edges[i][0]].push_back(mp(edges[i][1], weights[i]));
adj[edges[i][1]].push_back(mp(edges[i][0], weights[i]));
}
// for(int i = 0; i < n; ++i) {
// cout << i << ": ";
// for(int j = 0; j < adj[i].size(); ++j) {
// cout << "(" << adj[i][j].fi << ", " << adj[i][j].se << "); ";
// }
// cout << endl;
// }
vector<int> dist(n, INF);
vector<bool> visited(n, false);
dist[0] = 0;
visited[0] = true;
priority_queue<int> pq;
pq.push(0);
while(!pq.empty()) {
int curr = pq.top();
pq.pop();
int smallest_node = -1;
int second_smallest_n = -1;
int smallest_w = INF;
int second_smallest_w = INF;
for(auto next : adj[curr]) {
if(!visited[next.fi]) {
if(next.se <= smallest_w) {
second_smallest_w = smallest_w;
second_smallest_n = smallest_node;
smallest_w = next.se;
smallest_node = next.fi;
}
else if(next.se < second_smallest_w) {
second_smallest_w = next.se;
second_smallest_n = next.fi;
}
}
}
if(second_smallest_n == -1) {
continue;
}
if(visited[second_smallest_n]) {
continue;
}
// cout << "ssn: " << second_smallest_n << endl;
visited[second_smallest_n] = true;
dist[second_smallest_n] = dist[curr] + second_smallest_w;
pq.push(second_smallest_n);
}
// for(int i = 0; i < n; ++i) {
// cout << dist[i] << endl;
// }
int answer = INF;
for(int i = 0; i < k; ++i) {
answer = min(answer, dist[exits[i]]);
}
cout << answer << endl;
return 0;
}