Recently, I was solving the Graphs section of the CSES problemset and encountered this problem. I used dijkstra algorithm to solve it.
I generally use the template from here, but in this question, this implementation gave me WA. When I used another implementation using visited array, it gave AC.
WA code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
vector<vector<pair<ll,ll>>> adj,adj_rev;
vector<ll> d1,d2;
void dijkstra(){
set<pair<ll,ll>> st;
st.insert({0,1});
d1[1]=0;
while(!st.empty()){
ll node=st.begin()->second;
st.erase(st.begin());
for(auto it:adj[node]){
ll child=it.first,wt=it.second;
st.erase({d1[child],child});
if(d1[child]>d1[node]+wt){
d1[child]=d1[node]+wt;
st.insert({d1[child],child});
}
}
}
}
void dijkstra1(){
set<pair<ll,ll>> st;
ll n=adj.size()-1;
st.insert({0,n});
d2[n]=0;
while(!st.empty()){
ll node=st.begin()->second;
st.erase(st.begin());
for(auto it:adj_rev[node]){
ll child=it.first,wt=it.second;
st.erase({d2[child],child});
if(d2[child]>d2[node]+wt){
d2[child]=d2[node]+wt;
st.insert({d2[child],child});
}
}
}
}
int main(){
ll n,m;
cin>>n>>m;
adj=adj_rev=vector<vector<pair<ll,ll>>>(n+1);
d1=d2=vector<ll>(n+1,1e18);
while(m--){
ll a,b,c;
cin>>a>>b>>c;
adj[a].push_back({b,c});
adj_rev[b].push_back({a,c});
}
dijkstra();
dijkstra1();
ll ans=1e18;
for(int i=1;i<=n;i++){
for(auto it:adj[i]){
ans=min(ans,d1[i]+d2[it.first]+it.second/2);
}
}
cout<<ans;
return 0;
}
AC Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
vector<vector<pair<ll,ll>>> adj,adj_rev;
vector<ll> d1,d2;
void dijkstra(){
set<pair<ll,ll>> st;
ll n=adj.size()-1;
vector<bool> vis(n+1,false);
st.insert({0,1});
d1[1]=0;
while(!st.empty()){
ll node=st.begin()->second;
st.erase(st.begin());
if(vis[node]) continue;
vis[node]=true;
for(auto it:adj[node]){
ll child=it.first,wt=it.second;
if(d1[child]>d1[node]+wt){
d1[child]=d1[node]+wt;
st.insert({d1[child],child});
}
}
}
}
void dijkstra1(){
set<pair<ll,ll>> st;
ll n=adj.size()-1;
vector<bool> vis(n+1,false);
st.insert({0,n});
d2[n]=0;
while(!st.empty()){
ll node=st.begin()->second;
st.erase(st.begin());
if(vis[node]) continue;
vis[node]=true;
for(auto it:adj_rev[node]){
ll child=it.first,wt=it.second;
if(d2[child]>d2[node]+wt){
d2[child]=d2[node]+wt;
st.insert({d2[child],child});
}
}
}
}
int main(){
ll n,m;
cin>>n>>m;
adj=adj_rev=vector<vector<pair<ll,ll>>>(n+1);
d1=d2=vector<ll>(n+1,1e18);
while(m--){
ll a,b,c;
cin>>a>>b>>c;
adj[a].push_back({b,c});
adj_rev[b].push_back({a,c});
}
dijkstra();
dijkstra1();
ll ans=1e18;
for(int i=1;i<=n;i++){
for(auto it:adj[i]){
ans=min(ans,d1[i]+d2[it.first]+it.second/2);
}
}
cout<<ans;
return 0;
}
Naturally, I adopted the visited array approach and discarded the one before.
Now, using the visited array approach on this, I encountered WA again.
WA Code
#include<bits/stdc++.h>
using namespace std;
void dijkstra(vector<int> adj[],vector<int> &dist,vector<int> &par){
set<pair<int,int>> st;
par[1]=dist[1]=0;
st.insert({0,1});
int n=dist.size()-1;
bool vis[n+1]={false};
while(!st.empty()){
auto itr=*st.rbegin();
int node=itr.second,d=itr.first;
st.erase(prev(st.end()));
if(vis[node]) continue;
vis[node]=true;
for(auto it:adj[node]){
if(d+1>dist[it]){
st.insert({d+1,it});
dist[it]=d+1;
par[it]=node;
}
}
}
}
void solve(){
int n,m;
cin>>n>>m;
vector<int> adj[n+1];
vector<int> dist(n+1,INT_MIN);
vector<int> par(n+1,-1);
while(m--){
int a,b;
cin>>a>>b;
adj[a].push_back(b);
}
dijkstra(adj,dist,par);
if(par[n]==-1){
cout<<"IMPOSSIBLE\n";
return;
}
vector<int> ans;
int x=n;
while(x){
ans.push_back(x);
x=par[x];
}
reverse(ans.begin(),ans.end());
cout<<ans.size()<<'\n';
for(auto it:ans) cout<<it<<' ';
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
solve();
return 0;
}
Now I am very confused about what template to use for dijkstra, being a newbie to graphs. I would highly appreciate if someone helps.
