이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mx=1e5+9;
const ll inf=1e18;
ll dist[4][mx+9];
vector<pair<int,ll>>adj[mx];
int n,m,s,t,u,v;
ll dp[mx];
ll dp2[mx];
ll l;
void dikjstra(int node,int cnt)
{
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater < pair<ll,int> >>q;
for(int i=0; i<=n; i++)
{
dist[cnt][i]=inf;
}
q.push({0,node});
// cout<<dist[0][2]<<endl;
dist[cnt][node]=0;
while(!q.empty())
{
pair<ll,int>me=q.top();
q.pop();
int x=me.second;
ll cost=me.first;
// cout<<"TEST "<<x<<endl;
for(auto it:adj[x])
{
int node2=it.first;
// cout<<it.first<<" "<<it.second<<endl;
if(cost+it.second<dist[cnt][it.first])
{
// cout<<node2<<"xx"<<endl;
ll cost2=cost+it.second;
dist[cnt][it.first]=cost2;
q.push({(cost2),node2});
}
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin>>n>>m>>s>>t>>u>>v;
for(int i=0; i<m; i++)
{
ll x,y,c;
cin>>x>>y>>c;
adj[x].push_back({y,c});
adj[y].push_back({x,c});
}
dikjstra(s,0);
dikjstra(t,1);
dikjstra(u,2);
dikjstra(v,3);
l=dist[0][t];
queue<pair<ll,int>>q;
for(int i=1; i<=n; i++)
{
dp[i]=dp2[i]=inf;
}
int par[n+5];
ll ans=inf;
for(int i=1; i<=n; i++)
{
par[i]=-1;
}
q.push({0,s});
int vis[n+5];
memset(vis,0,sizeof(vis));
while(!q.empty())
{
pair<ll,int >me=q.front();
int x=me.second;
vis[x]=1;
ll cost=me.first;
q.pop();
dp[x]=min(dp[x],dist[3][x]);
for(auto it:adj[x])
{
ll cost2=me.first+it.second;
int z=it.first;
if(l-(cost2)==dist[1][z]&&!vis[z]&&dist[0][z]+dist[1][z]==l)
{
par[z]=x;
dp[it.first]=min(dp[it.first],dp[x]);
q.push({cost2,it.first});
}
}
}
q.push({0,t});
memset(vis,0,sizeof(vis));
for(int i=1; i<=n; i++)
{
par[i]=-1;
}
while(!q.empty())
{
pair<ll,int >me=q.front();
int x=me.second;
vis[x]=1;
ll cost=me.first;
q.pop();
// cout<<x<<endl;
dp2[x]=min(dp2[x],dist[3][x]);
for(auto it:adj[x])
{
ll cost2=me.first+it.second;
// cout<<it.first<<" "<<cost2<<" "<<dist[0][it.first]<<endl;
int z=it.first;
if(l-(cost2)==dist[0][z]&&!vis[z]&&dist[0][z]+dist[1][z]==l)
{
par[it.first]=x;
dp2[it.first]=min(dp2[it.first],dp2[x]);
q.push({cost2,it.first});
}
}
}
for(int i=1; i<=n; i++)
{
if(dist[0][i]+dist[1][i]==l)
{
ans=min(dist[2][i]+dp2[i],ans);
ans=min(dist[2][i]+dp[i],ans);
}}
ans=min(ans,dist[2][v]);
cout<<ans;
}
컴파일 시 표준 에러 (stderr) 메시지
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:93:12: warning: unused variable 'cost' [-Wunused-variable]
93 | ll cost=me.first;
| ^~~~
commuter_pass.cpp:126:12: warning: unused variable 'cost' [-Wunused-variable]
126 | ll cost=me.first;
| ^~~~
commuter_pass.cpp:77:9: warning: variable 'par' set but not used [-Wunused-but-set-variable]
77 | int par[n+5];
| ^~~
# | 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... |