This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
using pli = pair<long long, int>;
using ll = long long;
const int MN = 1e5 + 5;
vector<pii> adj[MN];
ll distU[MN], distV[MN], distS[MN], distT[MN], dpU[MN], dpV[MN];
bool vis[MN];
void dijkstra (int source, long long *dist) {
priority_queue<pli,vector<pli>,greater<pli>> pq;
dist[source] = 0; pq.push({0,source});
while (!pq.empty()) {
ll d = pq.top().first; int cur = pq.top().second; pq.pop();
if (d > dist[cur]) continue;
for (pii &p : adj[cur]) if (d + p.second < dist[p.first]) {
dist[p.first] = d + p.second;
pq.push({dist[p.first],p.first});
}
}
}
int main () {
int n,m,s,t,u,v;
scanf("%d %d %d %d %d %d",&n,&m,&s,&t,&u,&v);
while (m--) {
int a,b,c;
scanf ("%d %d %d",&a,&b,&c);
adj[a].emplace_back(b,c);
adj[b].emplace_back(a,c);
}
memset(distU,0x3f,sizeof distU); memset(distV,0x3f,sizeof distV); memset(distS,0x3f,sizeof distS); memset(distT,0x3f,sizeof distT);
dijkstra(u,distU); dijkstra(v,distV); dijkstra(s,distS); dijkstra(t,distT);
for (int i = 1; i <= n; i++) dpU[i] = distU[i], dpV[i] = distV[i];
queue<int> q; q.push(s);
while (!q.empty()) {
int cur = q.front(); q.pop(); vis[cur] = 1;
for (pii p : adj[cur]) if (!vis[p.first] && distS[p.first] + distT[p.first] == distS[t]) {
dpU[p.first] = min(dpU[p.first],dpU[cur]); dpV[p.first] = min(dpV[p.first],dpV[cur]);
q.push(p.first);
}
}
ll ret = LLONG_MAX;
for (int i = 1; i <= n; i++) ret = min({ret,dpU[i]+distV[i],dpV[i]+distU[i]});
printf ("%lld\n",ret);
return 0;
}
Compilation message (stderr)
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:24: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:27:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d %d %d",&a,&b,&c);
~~~~~~^~~~~~~~~~~~~~~~~~~~~
# | 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... |