| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 570850 | 1ne | Commuter Pass (JOI18_commuter_pass) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
struct point{
int64_t d,u,pp,bb;
};
struct cm {
bool operator()(const point& a, const point& b) const {
return a.d < b.d;
}
};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int64_t n,m;cin>>n>>m;
int64_t S,T;cin>>S>>T;
--S;--T;
int64_t U,V;cin>>U>>V;
--U;--V;
vector<vector<pair<int64_t,int64_t>>>adj(n);
for (int64_t i = 0;i<m;++i){
int64_t x,y,z;cin>>x>>y>>z;
--x;--y;
adj[x].push_back({y,z});
adj[y].push_back({x,z});
}
const int64_t mxn = 1e18;
priority_queue<pair<int64_t,pair<int64_t,int64_t>>>q;
vector<vector<int64_t>>dist(n,vector<int64_t>(2,mxn));
q.push({0,{U,0}});
q.push({0,{V,1}});
dist[U][0] = 0;
dist[V][1] = 0;
while(!q.empty()){
auto u = q.top().second;
q.pop();
for (auto x:adj[u.first]){
if (dist[x.first][u.second] > dist[u.first][u.second] + x.second){
dist[x.first][u.second] = dist[u.first][u.second] + x.second;
q.push({-dist[x.first][u.second],{x.first,u.second}});
}
}
}
int64_t ans = dist[U][1];
vector<int64_t>dis(n,mxn);
vector<pair<int64_t,int64_t>>mp(n);
auto bfs = [&](){
multiset<point,cm>qq;
qq.insert({0LL,S,dist[S][0],dist[S][1]});
dis[S] = 0LL;
while(!qq.empty()){
auto u = *qq.begin();
qq.erase(qq.begin());
mp.erase(u.u);
if (u.d > dis[u.u])continue;
if (u.u == T){
ans = min(ans,u.pp + u.bb);
continue;
}
for (auto x:adj[u.u]){
if (dis[x.first] > dis[u.u] + x.second){
auto it = qq.find({dis[x.first],x.first,mp[x.first].first,mp[x.first].second});
if (it!=qq.end())qq.erase(it);
dis[x.first] = dis[u.u] + x.second;
qq.insert({dis[x.first],x.first,min(u.pp,dist[x.first][0]),min(u.bb,dist[x.first][1])});
mp[x.first] = make_pair(min(u.pp,dist[x.first][0]),min(u.bb,dist[x.first][1]));
}
else if (dis[x.first] == dis[u.u] + x.second && !mp.empty()){
if (mp[x.first].first > min(u.pp,dist[x.first][0]) || mp[x.first].second > min(u.bb,dist[x.first][1])){
qq.insert({dis[x.first],x.first, min(u.pp,dist[x.first][0]),min(u.bb,dist[x.first][1])});
mp[x.first] = make_pair(min(u.pp,dist[x.first][0]),min(u.bb,dist[x.first][1]));
}
}
}
}
};
bfs();
cout<<ans<<'\n';
return 0;
}