이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ff first
#define ss second
#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define vi vector<int>
#define mii map<int,int>
#define pqb priority_queue<int>
#define pqs priority_queue<int,vi,greater<int> >
#define setbits(x) __builtin_popcountll(x)
#define zrobits(x) __builtin_ctzll(x)
#define mod 1000000007
#define inf 1e18
#define ps(x,y) fixed<<setprecision(y)<<x
#define mk(arr,n,type) type *arr=new type[n];
#define w(x) int x; cin>>x; while(x--)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);
// g->{i,j} i is the node and j is the wt
vector<vector<pii>> make_dag(vi &ds,vi &dv,int src,int dest,vector<vector<pii>> &g,int n)
{
vector<vector<pii>> dag(n+1);
for(int i=1;i<=n;i++)
{
for(auto x:g[i]) if(ds[i]+x.ss+dv[x.ff]==ds[dest]) dag[i].pb({x.ff,x.ss});
}
return dag;
}
void djkstra(int src,vi &dist,vector<vector<pii>> &g)
{
priority_queue<vi,vector<vi>,greater<vi>> pq;
pq.push({0,src,-1,0});
while(!pq.empty()){
vi temp=pq.top();pq.pop();
int node=temp[1],till=temp[0],p=temp[2],wt=temp[3];
if(dist[node]==inf || dist[node]==till){
// if(p!=-1) dag[p].pb({node,wt});
if(dist[node]==inf)
for(auto x:g[node]) pq.push({till+x.ss,x.ff,node,x.ss});
dist[node]=till;
}
}
}
vi topo(vector<vector<pii>> &g,int n,vi &vis)
{
vi inorder(n+1,0),topo;
queue<int> q;
for(int i=1;i<=n;i++) for(auto x:g[i]) inorder[x.ff]++;
for(int i=1;i<=n;i++) if(inorder[i]==0 && vis[i]==1) q.push(i);
while(!q.empty()){
int t=q.front();q.pop();
topo.pb(t);
for(auto node:g[t]){
inorder[node.ff]--;
if(inorder[node.ff]==0 && vis[node.ff]==1) q.push(node.ff);
}
}
return topo;
}
int s1(vector<vector<pii>> &inv_g,vi &topo,vi &du,vi &dv,int n)
{
int ans=inf;
vi dp(n+1,inf);
for(int i=0;i<topo.size();i++){
int mn=inf;
for(auto x:inv_g[topo[i]])
{
ans=min(ans,du[x.ff]+dp[x.ff]);
mn=min(mn,dp[x.ff]);
}
dp[topo[i]]=min(mn,dv[topo[i]]);
}
return ans;
}
int dfs(int node,vi &du,vector<vector<pii>> &dag,vi &dp)
{
if(dp[node]!=-1) return dp[node];
int ans=inf;
for(auto x:dag[node]) ans=min(ans,dfs(x.ff,du,dag,dp));
return (dp[node]=min(ans,du[node]));
}
int solve(vector<vector<pii>> &dag,int u,int v,vi &du,vi &dv,int n,int s)
{
int ans=du[v];
// vi tp=topo(dag,n);
// vector<vector<pii>> inv_g(n+1);
// for(int i=1;i<=n;i++){
// for(auto x:dag[i]) inv_g[x.ff].pb({i,x.ss});
// }
vi dp(n+1,-1);
dfs(s,dv,dag,dp);
for(int i=1;i<=n;i++)
if(dag[i].size()>0 && dp[i]!=-1)
ans=min(ans,du[i]+dp[i]);
return ans;
}
int32_t main()
{
fastio;
int n,m,s,t,u,v,x,y,wt;
cin>>n>>m>>s>>t>>u>>v;
vector<vector<pii>> g(n+1),dag_s;
for(int i=0;i<m;i++){
cin>>x>>y>>wt;
g[x].pb({y,wt});
g[y].pb({x,wt});
}
vi ds(n+1,inf),du(n+1,inf),dv(n+1,inf),dt(n+1,inf);
djkstra(s,ds,g);
djkstra(u,du,g);
djkstra(v,dv,g);
djkstra(t,dt,g);
dag_s=make_dag(ds,dt,s,t,g,n);
// for(int i=1;i<=n;i++){
// for(auto x:dag_s[i]) cout<<i<<"*"<<x.ff<<" "<<x.ss<<endl;
// }
// for(int i=1;i<=n;i++) cout<<dv[i]<<" ";
vi vis(n+1,0);
vector<vector<pii>> inv_g(n+1);
for(int i=1;i<=n;i++){
for(auto x:dag_s[i])
{
inv_g[x.ff].pb({i,x.ss});
vis[i]=1;vis[x.ff]=1;
}
}
vi tp=topo(dag_s,n,vis);
int ans=du[v];
ans=min(ans,solve(dag_s,u,v,du,dv,n,s));
ans=min(ans,solve(dag_s,v,u,dv,du,n,s));
ans=min(ans,s1(inv_g,tp,du,dv,n));
ans=min(ans,s1(inv_g,tp,dv,du,n));
cout<<ans<<"\n";
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
commuter_pass.cpp: In function 'void djkstra(long long int, std::vector<long long int>&, std::vector<std::vector<std::pair<long long int, long long int> > >&)':
commuter_pass.cpp:46:39: warning: unused variable 'p' [-Wunused-variable]
46 | int node=temp[1],till=temp[0],p=temp[2],wt=temp[3];
| ^
commuter_pass.cpp:46:49: warning: unused variable 'wt' [-Wunused-variable]
46 | int node=temp[1],till=temp[0],p=temp[2],wt=temp[3];
| ^~
commuter_pass.cpp: In function 'long long int s1(std::vector<std::vector<std::pair<long long int, long long int> > >&, std::vector<long long int>&, std::vector<long long int>&, std::vector<long long int>&, long long int)':
commuter_pass.cpp:75:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for(int i=0;i<topo.size();i++){
| ~^~~~~~~~~~~~
# | 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... |