# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
75170 | bogdan10bos | Commuter Pass (JOI18_commuter_pass) | C++14 | 2041 ms | 42296 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
//#define FILE_IO
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, int> pli;
int N, M, S, T, U, V;
vector<int> pth;
vector<pii> edg[100005];
priority_queue< pli, vector<pli>, greater<pli> > pq;
class Dijkstra
{
public:
int nod;
LL d[100005];
void dijkstra(int _nod)
{
nod = _nod;
for(int i = 1; i <= N; i++) d[i] = 1LL << 60;
while(!pq.empty()) pq.pop();
d[nod] = 0;
pq.push({0LL, nod});
while(!pq.empty())
{
int nod = pq.top().second;
LL val = pq.top().first;
pq.pop();
if(d[nod] != val) continue;
for(auto &e: edg[nod])
if(d[e.first] > val + e.second)
{
d[e.first] = val + e.second;
pq.push({val + e.second, e.first});
}
}
}
LL getd(int x) { return d[x]; }
}dS, dT, dU, dV;
int main()
{
#ifdef FILE_IO
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
scanf("%d%d", &N, &M);
scanf("%d%d", &S, &T);
scanf("%d%d", &U, &V);
for(int i = 1; i <= M; i++)
{
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
edg[x].push_back({y, z});
edg[y].push_back({x, z});
}
dS.dijkstra(S);
dT.dijkstra(T);
dU.dijkstra(U);
dV.dijkstra(V);
LL ans = dU.getd(V);
LL dST = dS.getd(T);
for(int i = 1; i <= N; i++)
if(dS.getd(i) + dT.getd(i) == dST)
pth.push_back(i);
for(auto x: pth)
for(auto y: pth)
ans = min(ans, dU.getd(x) + dV.getd(y));
printf("%lld\n", ans);
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |