| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 526844 | zhangjishen | Commuter Pass (JOI18_commuter_pass) | C++98 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
template<typename T> bool chkmin(T &a, T b){return b < a ? a = b, 1 : 0;}
template<typename T> bool chkmax(T &a, T b){return b > a ? a = b, 1 : 0;}
typedef long long ll;
typedef pair<ll, int> pii;
const int MAXN = 1e5 + 10;
const ll inf = 1e18;
int n, m, k, ext[MAXN];
ll f1[MAXN], f2[MAXN];
vector<pair<int, int> > adj[MAXN];
// update f1[u] and f2[u] with k(path length)
void update(int u, ll d){
if(d < f1[u])
f2[u] = f1[u], f1[u] = d;
else if(d < f2[u])
f2[u] = d;
}
priority_queue<pii, vector<pii>, greater<pii> > q;
bool fro[MAXN]; // frontier
void dijkstra(){
for(int i = 1; i <= n; i++)
f1[i] = f2[i] = inf;
for(int i = 1; i <= k; i++){
int u = ext[i];
f1[u] = f2[u] = 0; q.push(mp(0, u));
}
while(!q.empty()){
pii p = q.top(); q.pop();
int u = p.se;
if(fro[u]) continue; // already inducted on u
fro[u] = true; // DP of u finished
for(int i = 0; i < (int)adj[u].size(); i++){
int v = adj[u][i].fi, w = adj[u][i].se;
if(p.fi + w < f2[v]){
update(v, p.fi + w);
q.push(mp(f2[v], v));
}
}
}
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
// input
n = N, m = M, k = K;
for(int i = 0; i < m; i++){
int a = R[i][0] + 1, b = R[i][1] + 1, c = L[i];
adj[a].pb(mp(b, c));
adj[b].pb(mp(a, c));
}
for(int i = 1; i <= k; i++)
ext[i] = P[i - 1] + 1;
// dijkstra
dijkstra();
return (int)f2[1];
}