#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define X first
#define Y second
const int maxn = 100005;
const ll inf = 1e18;
struct node {
int x;
ll val;
node(int _x = 0, ll _val = 0) {
x = _x; val = _val;
};
bool operator < (node a) const {
return a.val<val;
}
};
int n,m,a,b,c,d;
ll da[maxn], db[maxn], dc[maxn], dd[maxn];
pair<ll,ll> mn[maxn];
vector<pair<int,ll>> way[maxn];
ll ans;
void ssspt(int u, ll* dist) {
priority_queue<node> heap;
for(int i=1;i<=n;i++) dist[i] = inf;
dist[u] = 0;
heap.push(node(u,0));
while(!heap.empty()) {
auto t = heap.top(); heap.pop();
u = t.x;
if(dist[u]<t.val) continue;
for(auto nxt : way[u]) {
int v = nxt.X; ll val = nxt.Y;
if(dist[v] > dist[u]+val) {
dist[v] = dist[u]+val;
heap.push(v);
}
}
}
}
void sssp(int u, ll* dist) {
priority_queue<node> heap;
for(int i=1;i<=n;i++) {
dist[i] = inf;
mn[i] = {dc[i], dd[i]};
}
dist[u] = 0;
heap.push(node(u,0));
while(!heap.empty()) {
auto t = heap.top(); heap.pop();
u = t.x;
if(dist[u]<t.val) continue;
if(dist[u]+db[u]==db[a]) {
// printf("u = %d : %lld + %lld or %lld + %lld\n",u,mn[u].X,dd[u],mn[u].Y,dc[u]);
ans = min(ans, mn[u].X + dd[u]);
ans = min(ans, mn[u].Y + dc[u]);
}
for(auto nxt : way[u]) {
int v = nxt.X; ll val = nxt.Y;
if(dist[v] > dist[u]+val) {
dist[v] = dist[u]+val;
heap.push(v);
}
if(dist[v] == dist[u]+val) {
mn[v].X = min(mn[v].X,mn[u].X);
mn[v].Y = min(mn[v].Y,mn[u].Y);
}
}
}
}
int main() {
scanf("%d%d",&n,&m);
scanf("%d%d%d%d",&a,&b,&c,&d);
for(int i=0;i<m;i++) {
int x,y; ll val;
scanf("%d%d%lld",&x,&y,&val);
way[x].pb({y,val}); way[y].pb({x,val});
}
ssspt(b,db);
ssspt(c,dc);
ssspt(d,dd);
return 0;
ans = dd[c];
sssp(a,da);
// for(int i=1;i<=n;i++) {
// printf("%d\n",i);
// printf("--- dist from a = %lld\n",da[i]);
// printf("--- dist from b = %lld\n",db[i]);
// printf("--- dist from c = %lld\n",dc[i]);
// printf("--- dist from d = %lld\n",dd[i]);
// }
printf("%lld",ans);
}
Compilation message
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:73:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&m);
^
commuter_pass.cpp:74:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d",&a,&b,&c,&d);
^
commuter_pass.cpp:77:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%lld",&x,&y,&val);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2050 ms |
14964 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2036 ms |
15020 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
15020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2050 ms |
14964 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
