| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 41163 | ngkan146 | Commuter Pass (JOI18_commuter_pass) | C++98 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct edge{
int v, w;
edge(int v=0,int w=0): v(v), w(w) {}
};
int n,m,s,t,u,v;
vector <edge> G[100005];
vector <int> dag[100005];
ll dis[100005], disS[100005], disU[100005], disV[100005];
bool visited[100005];
priority_queue <pair<long long,int>, vector<pair<long long,int> >, greater<pair<long long, int> > > pq;
void dijkstra(int root){
fill(dis+1,dis+n+1, (ll) 1e18);
fill(visited,visited+n+1,0);
dis[root] = 0;
pq.push(pair<ll,int>(0ll, root));
while(pq.size()){
int u = pq.top().second;
pq.pop();
if (visited[u]) continue;
visited[u] = 1;
for(auto v: G[u]){
if (dis[v.v] > dis[u] + v.w)
dis[v.v] = dis[u] + v.w,
pq.push(pair<ll,int>(dis[v.v], v.v));
}
}
}
void trailBack(int u){
if (visited[u]) return;
visited[u] = 1;
for(auto v: G[u]){
if (disS[v.v] == disS[u] - v.w)
dag[v.v].push_back(u),
trailBack(v.v);
}
}
ll ans = (ll) 1e18;
ll dfs(int u){
ll mini = (ll) disV[u];
for(int v: dag[u]){
mini = min(mini, dfs(v));
}
ans = min(ans, disU[u] + mini);
return mini;
}
int main(){
iostream::sync_with_stdio(0);
cin >> n >> m >> s >> t >> u >> v;
for(int i=1;i<=m;i++){
int a,b,c;
cin >> a >> b >> c;
G[a].push_back(edge(b, c));
G[b].push_back(edge(a, c));
}
dijkstra(s);
for(int i=1;i<=n;i++) disS[i] = dis[i];
fill(visited+1,visited+n+1,0);
trailBack(t);
dijkstra(u);
for(int i=1;i<=n;i++) disU[i] = dis[i];
ans = disU[v];
dijkstra(v);
for(int i=1;i<=n;i++) disV[i] = dis[i];
dfs(s);
swap(disU, disV);
dfs(s);
cout << ans;
}