| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1315611 | jokuk | Commuter Pass (JOI18_commuter_pass) | C++17 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
int main()
{
cin.tie(nullptr)->sync_with_stdio(false);
int n,r,s,t,start,stop;
cin>>n;
cin>>r;
cin>>s;
cin>>t;
cin>>start;
cin>>stop;
vector<vector<pair<int,long long int>>> adj(n);
for(int i=0;i<r;i++)
{
int u,v;
long long int w;
cin>>u;
cin>>v;
cin>>w;
u--;
v--;
adj[u].push_back({v,w});
adj[v].push_back({u,w});
}
priority_queue<pair<long long int ,int>> q;
long long int distx[n+1],disty[n+1];
for(int i=1;i<=n;i++)
{
distx[i]=LLONG_MAX;
}
distx[start]=disty[stop]=0;
q.emplace(0,start);
while(!q.empty())
{
auto [w, u] = q.top();
q.pop();
w=-w;
if(distx[u]!=w)
{
continue;
}
for (auto [v,ww] : adj[u])
{
if (distx[v]>ww+w)
{
q.emplace(-(distx[v]=ww+w),v);
}
}
}
q.emplace(0,stop);
while(!q.empty())
{
auto [w, u] = q.top();
q.pop();
w=-w;
if(disty[u]!=w)
{
continue;
}
for (auto [v, ww] : adj[u])
{
if (disty[v]>ww+w)
{
q.emplace(-(disty[v]=ww+w),v);
}
}
}
priority_queue<tuple<long long int,long long int,long long int,long long int,int>> q1;// reminder dist, minx+miny, minx, miny, u
pair<long long int,long long int> dist[n+1];
for (int i = 1; i <= n; i++)
{
dist[i] = make_pair(LLONG_MAX, LLONG_MAX);
}
dist[s].make_pair(0,distx[s]+disty[s]);
q1.emplace(0,-(distx[s]+disty[s]),-distx[s],-disty[s],s);
while(!q1.empty())
{
auto [w, sum, minx, miny, u] = q1.top();
q1.pop();
w=-w;
sum=-sum;
minx=-minx;
miny=-miny;
if(make_pair(w,sum)!=dist[u])
{
continue;
}
for (auto [v, ww] : adj[u])
{
long long int nw = w+ww, nx=min(minx,distx[v]),ny=min(miny,disty[v]),ns=nx+ny;
if (dist[v].first>nw)
q1.emplace(-(dist[v].first = nw),-(dist[v].second=ns),-nx,-ny,v);
else if (dist[v].first == nw && dist[v].second > ns)
q1.emplace(-(dist[v].first = nw), -(dist[v].second = ns), -nx, -ny, v);
}
}
cout<<min(dist[t.second],distx[stop])<<"\n";
}