이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in array<int, 2>
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define MX (int)3e5+5
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
vector<in> adj[MX];
void dijsktra(int n, int src, vector<int> &dist)
{
priority_queue<in> pq;
dist.assign(n+1, INF);
pq.push({dist[src] = 0, src});
while(pq.size())
{
auto [wp, U] = pq.top(); wp = -wp; pq.pop();
if(dist[U] < wp)
continue;
for(auto [v, w]: adj[U])
{
if(dist[v] > (dist[U]+w))
{
dist[v] = dist[U]+w;
pq.push({-dist[v], v});
}
}
}
return;
}
signed main()
{
fast();
int n, m;
cin >> n >> m;
int S, T, U, V;
cin >> S >> T >> U >> V;
while(m--)
{
int u, v, w;
cin >> u >> v >> w;
adj[u].pb({v, w});
adj[v].pb({u, w});
}
vector<int> d1, d2;
dijsktra(n, U, d1); dijsktra(n, V, d2);
vector<int> dist; dist.assign(n+1, INF);
/*for(int i = 1; i <= n; i++)
cout << d1[i] << " ";
cout << endl;
for(int i = 1; i <= n; i++)
cout << d2[i] << " ";
cout << endl;*/
int cnt[4][n+1];
for(int i = 1; i <= n; i++)
{
for(int j = 1; j < 4; j++)
cnt[j][i] = INF;
}
cnt[1][S] = d1[S]; cnt[2][S] = d2[S]; cnt[3][S] = d1[S]+d2[S];
dist.assign(n+1, INF);
priority_queue<in> pq;
pq.push({dist[S] = 0, S});
while(pq.size())
{
auto [wp, u] = pq.top(); wp = -wp; pq.pop();
if(dist[u] < wp)
continue;
for(auto [v, w]: adj[u])
{
if(dist[v] > (dist[u]+w))
{
dist[v] = dist[u]+w;
pq.push({-dist[v], v});
cnt[1][v] = min(cnt[1][u], d1[v]);
cnt[2][v] = min(cnt[2][u], d2[v]);
cnt[3][v] = min(cnt[3][u], min(d1[v] + cnt[2][u], d2[v] + cnt[1][u]));
cnt[3][v] = min(cnt[3][v], d1[v]+d2[v]);
}
else if(dist[v] == (dist[u]+w))
{
cnt[1][v] = min(cnt[1][v], cnt[1][u]);
cnt[2][v] = min(cnt[2][v], cnt[2][u]);
cnt[3][v] = min(cnt[3][v], min(d1[v] + cnt[2][u], d2[v] + cnt[1][u]));
cnt[3][v] = min(cnt[3][v], cnt[3][u]);
}
}
}
int ans = min(d1[V], cnt[3][T]);
cout << ans << "\n";
return 0;
}
# | 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... |