#include <bits/stdc++.h>
using namespace std;
vector<int> g[100007],h[100007],k[100007];
vector<long long> w[100007];
long long d[3][100007],dpl[2][100007],dpd[2][100007];
int n,degin[100007],ord[100007],cur;
bool st[100007];
void djikstra(int s,int a)
{
priority_queue<pair<long long,int> > pq;
fill(d[a],d[a]+100007,-1LL);
d[a][s]=0;
for(int i=0;i<g[s].size();i++) pq.push(make_pair(-w[s][i],g[s][i]));
while(!pq.empty())
{
long long t=-pq.top().first;
int x=pq.top().second;
pq.pop();
if(d[a][x]==-1)
{
d[a][x]=t;
for(int i=0;i<g[x].size();i++) pq.push(make_pair(-t-w[x][i],g[x][i]));
}
}
}
void praviDAG(int s,int a)
{
priority_queue<pair<long long,pair<int,int> > > pq;
fill(d[a],d[a]+100007,-1);
d[a][s]=0;
for(int i=0;i<g[s].size();i++) pq.push(make_pair(-w[s][i],make_pair(g[s][i],s)));
while(!pq.empty())
{
long long t=-pq.top().first;
int x=pq.top().second.first,y=pq.top().second.second;
pq.pop();
if(d[a][x]==-1)
{
d[a][x]=t;
for(int i=0;i<g[x].size();i++) pq.push(make_pair(-t-w[x][i],make_pair(g[x][i],x)));
}
if(d[a][x]==t)
{
h[y].push_back(x);
k[x].push_back(y);
}
}
}
void toposort()
{
queue<int> q;
for(int i=1;i<=n;i++) deginy[i]=k[i].size();
for(int i=1;i<=n;i++) if(degin[i]==0) q.push(i);
while(!q.empty())
{
int u=q.front();
ord[cur++]=u;
q.pop();
for(int i=0;i<h[u].size();i++)
{
degin[h[u][i]]--;
if(degin[h[u][i]]==0) q.push(h[u][i]);
}
}
}
int main()
{
int m,s,t,u,v;
scanf("%d%d%d%d%d%d",&n,&m,&s,&t,&u,&v);
for(int i=0;i<m;i++)
{
int t1,t2;
long long t3;
scanf("%d%d%lld",&t1,&t2,&t3);
g[t1].push_back(t2);
g[t2].push_back(t1);
w[t1].push_back(t3);
w[t2].push_back(t3);
}
djikstra(u,0);
djikstra(v,1);
praviDAG(s,2);
toposort();
for(int i=0;i<cur;i++)
{
dpl[0][ord[i]]=d[0][ord[i]];
dpl[1][ord[i]]=d[1][ord[i]];
for(int j=0;j<k[ord[i]].size();j++)
{
dpl[0][ord[i]]=fmin(dpl[0][ord[i]],dpl[0][k[ord[i]][j]]);
dpl[1][ord[i]]=fmin(dpl[1][ord[i]],dpl[1][k[ord[i]][j]]);
}
}
st[t]=true;
for(int i=cur-1;i>=0;i--)
{
dpd[0][ord[i]]=d[0][ord[i]];
dpd[1][ord[i]]=d[1][ord[i]];
for(int j=0;j<h[ord[i]].size();j++) if(st[h[ord[i]][j]])
{
st[ord[i]]=true;
dpd[0][ord[i]]=fmin(dpd[0][ord[i]],dpd[0][h[ord[i]][j]]);
dpd[1][ord[i]]=fmin(dpd[1][ord[i]],dpd[1][h[ord[i]][j]]);
}
}
long long minimum=d[0][v];
for(int i=1;i<=n;i++) if(st[i]) minimum=fmin(minimum,dpd[0][i]+dpl[1][i]);
for(int i=1;i<=n;i++) if(st[i]) minimum=fmin(minimum,dpd[1][i]+dpl[0][i]);
printf("%lld",minimum);
}
Compilation message
commuter_pass.cpp: In function 'void djikstra(int, int)':
commuter_pass.cpp:13:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[s].size();i++) pq.push(make_pair(-w[s][i],g[s][i]));
~^~~~~~~~~~~~
commuter_pass.cpp:22:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[x].size();i++) pq.push(make_pair(-t-w[x][i],g[x][i]));
~^~~~~~~~~~~~
commuter_pass.cpp: In function 'void praviDAG(int, int)':
commuter_pass.cpp:31:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[s].size();i++) pq.push(make_pair(-w[s][i],make_pair(g[s][i],s)));
~^~~~~~~~~~~~
commuter_pass.cpp:40:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[x].size();i++) pq.push(make_pair(-t-w[x][i],make_pair(g[x][i],x)));
~^~~~~~~~~~~~
commuter_pass.cpp: In function 'void toposort()':
commuter_pass.cpp:52:24: error: 'deginy' was not declared in this scope
for(int i=1;i<=n;i++) deginy[i]=k[i].size();
^~~~~~
commuter_pass.cpp:52:24: note: suggested alternative: 'degin'
for(int i=1;i<=n;i++) deginy[i]=k[i].size();
^~~~~~
degin
commuter_pass.cpp:59:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<h[u].size();i++)
~^~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:88:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<k[ord[i]].size();j++)
~^~~~~~~~~~~~~~~~~
commuter_pass.cpp:99:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<h[ord[i]].size();j++) if(st[h[ord[i]][j]])
~^~~~~~~~~~~~~~~~~
commuter_pass.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d%d%d",&n,&m,&s,&t,&u,&v);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%lld",&t1,&t2,&t3);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
