| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 367450 | Sparky_09 | 구경하기 (JOI13_watching) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "crocodile.h"
#include "bits/stdc++.h"
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define trav(a, x) for(auto& a : x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<pii> vpi;
template <class T>
void rd(T &x) {
int sgn = 1;
char ch;
x = 0;
for (ch = getchar(); (ch < '0' || ch > '9') && ch != '-'; ch = getchar()) ;
if (ch == '-') ch = getchar(), sgn = -1;
for (; '0' <= ch && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
x *= sgn;
}
template <class T>
void wr(T x) {
if (x < 0) putchar('-'), wr(-x);
else if (x < 10) putchar(x + '0');
else wr(x / 10), putchar(x % 10 + '0');
}
void usaco(string s){
freopen((s+".in").c_str(), "r", stdin);
freopen((s+".out").c_str(), "w", stdout);
}
const int mxn = 100005;
int n, m, vis[mxn], dist[mxn][2];
vector<pair<int,int>> adj[mxn];
priority_queue<pair<int,int>> pq;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
n=N;m=M;
rep(i,0,m){
adj[R[i][0]+1].emplace_back(L[i],R[i][1]+1);
adj[R[i][1]+1].emplace_back(L[i],R[i][0]+1);
}
memset(dist, 0x3f, sizeof dist);
rep(i,0,K){
dist[P[i]+1][0] = dist[P[i]+1][1] = 0;
vis[P[i]+1] = 1;
pq.push({0,P[i]+1});
}
while(vis[1]!=2){
int cost = -pq.top().first;
int nod = pq.top().second; pq.pop();
if(vis[nod]==2) continue;
if(vis[nod]==1){
if(nod==1) return cost;
vis[nod] = 2;
for(auto i: adj[nod]){
int c = i.first, b = i.second;
if(vis[b] != 2 && cost+c < dist[b][1]){
dist[b][1] = cost+c;
if(dist[b][1] < dist[b][0]) swap(dist[b][1] , dist[b][0]);
pq.push({-(cost+c), b});
}
}
}
else vis[nod] = 1;
}
return -1;
}