이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fir first
#define sec second
#define pdd pair<double, double>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pmax pair<__int128, __int128>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
using namespace std;
int dx[4]={0, 1, 0, -1}, dy[4]={1, 0, -1 , 0};
const int mxN=100020;
const int mxM=2500000;
const int mxK=105;
const int MOD=1000000007;
const ll INF=1000000000000000001;
int N, M, S, T, U, V;
vector <pll> v[mxN];
ll dis[4][mxN];
priority_queue <pll> pq;
bool Chk[mxN];
vector <int> rv[2][mxN];
int rdeg[mxN];
queue <int> que;
ll sub[2][mxN];
ll ans=INF;
void dijkstra(int st, int idx)
{
while(!pq.empty()) pq.pop();
for(int i=1;i<=N;i++) Chk[i]=false;
for(int i=1;i<=N;i++) dis[idx][i]=INF;
dis[idx][st]=0;
pq.push({0, st});
while(!pq.empty())
{
int now=pq.top().sec;
pq.pop();
if(Chk[now]) continue;
Chk[now]=true;
for(pll nxt : v[now])
{
if(dis[idx][nxt.fir]>dis[idx][now]+nxt.sec)
{
dis[idx][nxt.fir]=dis[idx][now]+nxt.sec;
pq.push({-dis[idx][nxt.fir], nxt.fir});
}
}
}
}
void dfs0(int now)
{
Chk[now]=true;
for(pll nxt : v[now]) if(dis[0][now]+dis[1][nxt.fir]+nxt.sec==dis[0][T])
{
rv[0][now].push_back(nxt.fir);
rv[1][nxt.fir].push_back(now);
rdeg[now]++;
if(!Chk[nxt.fir]) dfs0(nxt.fir);
}
}
void dfs1(int now)
{
Chk[now]=true;
sub[0][now]=dis[3][now];
sub[1][now]=dis[2][now];
for(int nxt : rv[0][now])
{
if(!Chk[nxt]) dfs1(nxt);
sub[0][now]=min(sub[0][now], sub[0][nxt]);
sub[1][now]=min(sub[1][now], sub[1][nxt]);
}
}
int main()
{
gibon
cin >> N >> M >> S >> T >> U >> V;
for(int i=0;i<M;i++)
{
int a, b, c;
cin >> a >> b >> c;
v[a].emplace_back(b, c);
v[b].emplace_back(a, c);
}
dijkstra(S, 0);
dijkstra(T, 1);
dijkstra(U, 2);
dijkstra(V, 3);
/*for(int i=0;i<4;i++)
{
for(int j=1;j<=N;j++)
{
printf("dis[%d][%d]=%lld\n", i, j, dis[i][j]);
}
}*/
for(int i=1;i<=N;i++) Chk[i]=false;
dfs0(S);
for(int i=1;i<=N;i++) if(Chk[i] && !rdeg[i]) que.push(i);
while(!que.empty())
{
int now=que.front();
que.pop();
if(now==T) continue;
Chk[now]=false;
for(int nxt : rv[1][now])
{
rdeg[nxt]--;
if(!rdeg[nxt]) que.push(nxt);
}
}
vector <int> tmp;
for(int i=1;i<=N;i++)
{
if(!Chk[i])
{
rv[0][i].clear(); rv[1][i].clear();
continue;
}
tmp.clear();
for(int ele : rv[0][i]) if(Chk[ele]) tmp.push_back(ele);
swap(tmp, rv[0][i]);
tmp.clear();
for(int ele : rv[1][i]) if(Chk[ele]) tmp.push_back(ele);
swap(tmp, rv[1][i]);
}
for(int i=1;i<=N;i++) Chk[i]=false;
dfs1(S);
for(int i=1;i<=N;i++) if(Chk[i])
{
ans=min(ans, dis[2][i]+sub[0][i]);
ans=min(ans, dis[3][i]+sub[1][i]);
}
ans=min(ans, dis[2][V]);
cout << ans;
}
# | 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... |