이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//chockolateman
#include<bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
long long N,M,dist[100005],dist_U[100005],dist_V[100005],S,T,U,V;
bool visited[100005];
vector<pair<long long,long long>> adj[100005];
vector<long long> can_give_minimum[100005],free_edges[100005],reverse_free[100005]; //tthe DUG but reverse
void Dijsktra(long long start)
{
for(long long i = 1 ; i <= N ; i++)
{
dist[i] = INF;
visited[i] = false;
can_give_minimum[i].clear();
}
dist[start] = 0;
priority_queue<pair<long long,long long>> q;
q.push({0,start});
while(!q.empty())
{
long long v = q.top().second;
q.pop();
if(visited[v])
continue;
visited[v] = true;
for(auto e : adj[v])
{
long long u = e.first;
long long w = e.second;
if(dist[v] + w < dist[u])
{
dist[u] = dist[v] + w;
can_give_minimum[u].clear();
can_give_minimum[u].push_back(v);
q.push({-dist[u],u});
}
else if(dist[v] + w == dist[u])
can_give_minimum[u].push_back(v);
}
}
}
void direct_egdes(long long v)
{
if(visited[v])
return;
visited[v] = true;
for(auto u : can_give_minimum[v])
{
free_edges[u].push_back(v);
reverse_free[v].push_back(u);
direct_egdes(u);
}
}
void dfs_enter(long long v)
{
if(visited[v])
return;
visited[v] = true;
for(auto u : reverse_free[V]) //basically reverse free edges
{
dfs_enter(u);
dist_U[v] = min(dist_U[v],dist_U[u]);
}
}
void dfs_leave(long long v)
{
if(visited[v]) //used also as visited
return;
visited[v] = true;
for(auto u : free_edges[v])
{
dfs_leave(u);
dist_V[v] = min(dist_V[v],dist_V[u]);
}
}
int main()
{
scanf("%lld%lld%lld%lld%lld%lld",&N,&M,&S,&T,&U,&V);
for(long long a,b,w,i = 1 ; i <= M ; i++)
{
scanf("%lld%lld%lld",&a,&b,&w);
adj[a].push_back({b,w});
adj[b].push_back({a,w});
}
Dijsktra(U);
for(int i = 1 ; i <= N ; i++)
dist_U[i] = dist[i];
long long ans = dist[V];
Dijsktra(V);
for(int i = 1 ; i <= N ; i++)
dist_V[i] = dist[i];
Dijsktra(S);
memset(visited,false,sizeof(visited));
direct_egdes(T);
memset(visited,false,sizeof(visited));
for(int i = 1 ; i <= N ; i++)
dfs_enter(i);
memset(visited,false,sizeof(visited));
for(int i = 1 ; i <= N ; i++)
dfs_leave(i);
for(int i = 1 ; i <= N ; i++)
ans = min(ans,dist_U[i] + dist_V[i]);
swap(U,V);
Dijsktra(U);
for(int i = 1 ; i <= N ; i++)
dist_U[i] = dist[i];
Dijsktra(V);
for(int i = 1 ; i <= N ; i++)
dist_V[i] = dist[i];
memset(visited,false,sizeof(visited));
for(int i = 1 ; i <= N ; i++)
dfs_enter(i);
memset(visited,false,sizeof(visited));
for(int i = 1 ; i <= N ; i++)
dfs_leave(i);
for(int i = 1 ; i <= N ; i++)
ans = min(ans,dist_U[i] + dist_V[i]);
printf("%lld\n",ans);
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:88:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
88 | scanf("%lld%lld%lld%lld%lld%lld",&N,&M,&S,&T,&U,&V);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:91:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
91 | scanf("%lld%lld%lld",&a,&b,&w);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |