| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 635675 | PoonYaPat | Commuter Pass (JOI18_commuter_pass) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
typedef tuple<ll,ll,ll> t;
ll n,m,st,u,v,en,ans=LLONG_MAX;
ll ds[100001],du[100001],dv[100001];
vector<pii> adj[100001];
vector<int> adj2[100001];
priority_queue<pii, vector<pii>, greater<pii>> q;
priority_queue<t, vector<t>, greater<t>> pq;
void dij(ll *dis, int start) {
bool vis[100001];
memset(vis,0,sizeof(vis));
for (int i=1; i<=n; ++i) dis[i]=LLONG_MAX;
dis[start]=0;
q.push({0,start});
while (!q.empty()) {
pii a=q.top();
q.pop();
ll node=a.second;
if (vis[node]) continue;
vis[node]=true;
for (auto s : adj[node]) {
ll des=s.first, w=s.second;
if (dis[des]>dis[node]+w) {
dis[des]=dis[node]+w;
q.push({dis[des],des});
}
}
}
}
void dij2(ll *dis, int start) {
bool vis[100001];
memset(vis,0,sizeof(vis));
for (int i=1; i<=n; ++i) dis[i]=LLONG_MAX;
dis[start]=0;
pq.push({0,start,0});
while (!pq.empty()) {
ll node, par, d;
tie (d,node,par)=pq.top();
pq.pop();
if (dis[node]=d) adj2[node].push_back(par);
if (vis[node]) continue;
vis[node]=true;
for (auto s : adj[node]) {
ll des=s.first, w=s.second;
if (dis[des]>=dis[node]+w) {
dis[des]=dis[node]+w;
pq.push({dis[des],des,node});
}
}
}
}
multiset<ll> udis,vdis;
int cnt;
void dfs(int x) {
++cnt;
if (cnt>n) return 1;
udis.insert(du[x]);
vdis.insert(dv[x]);
if (x==st) ans=min(ans,*(udis.begin())+*(vdis.begin()));
for (auto s : adj2[x]) dfs(s);
udis.erase(udis.find(du[x]));
vdis.erase(vdis.find(dv[x]));
}
void dfs2(int x) {
ans=min(ans,dv[x]);
for (auto s : adj2[x]) dfs2(s);
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin>>n>>m>>st>>en>>u>>v;
for (int i=0; i<m; ++i) {
ll a,b,w;
cin>>a>>b>>w;
adj[a].push_back(pii(b,w));
adj[b].push_back(pii(a,w));
}
dij(du,u);
dij(dv,v);
if (st==u) {
dfs2(en);
cout<<min(ans,du[v]);
}
dij2(ds,st);
dfs(en);
cout<<min(ans,du[v]);
}