#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define in insert
#define vll vector<ll>
#define endl "\n"
#define pll pair<ll,ll>
#define all(x) (x).begin() , (x).end()
#define f first
#define s second
#define pr(x) cout<<x<<endl;
#define pr2(x,y) cout<<x<<" "<<y<<endl;
#define pr3(x,y,z) cout<<x<<" "<<y<<endl;
#define prv(v) for(auto x:v) cout<<x<<" ";
#define ffs fflush(stdout);
#define int ll
#define sz(x) (ll)x.size()
using namespace std;
const ll MOD = 1e9+7;
const ll INF = LLONG_MAX;
const ll LOG = 29;
#define PI 3.141592653589793238
const ll N =(1e5+5);
ll fact[N];
long long binpow(long long a, long long b) {
a%=MOD;
long long res = 1;
while (b > 0) {
if (b & 1)
res = (res * a)%MOD;
a = (a * a)%MOD;
b >>= 1;
}
res%=MOD;
return res;
}
void ini(){
fact[0] = 1;
for(int i = 1;i < N;i++){
fact[i] = (fact[i-1] * i)%MOD;
}
}
ll ncr(ll n,ll r){
ll ret = fact[n];
ret = (ret * binpow(fact[r],MOD-2))%MOD;
ret = (ret * binpow(fact[n-r],MOD-2))%MOD;
return ret;
}
struct lol
{
ll to;
ll cst;
};
ll n,m;
ll s,t;
ll u,v;
vector<lol> adj[N];
ll dis[N][2];
pll dis2[N][2];//dis[x] {shortest path from s,shortest path of all the nodes which lie on the shortest path from s to x to u}
void dijk(ll x){
priority_queue<pll,vector<pll>,greater<pll>> pq;
pq.push(mp(0,x));
ll i = 0;
if(x == v)i = 1;
dis[x][i] = 0;
while(!pq.empty()){
pll p = pq.top();
pq.pop();
for(auto y:adj[p.s]){
if(dis[y.to][i] > dis[p.s][i] + y.cst){
dis[y.to][i] = dis[p.s][i] + y.cst;
pq.push(mp(dis[y.to][i],y.to));
}
}
}
}
void dijk2(ll x){
priority_queue<pair<pll,ll>,vector<pair<pll,ll>>,greater<pair<pll,ll> >> pq;
ll i;
if(x == s) i = 0;
else i = 1;
pair<pll,ll> lolz;
lolz.f.f = 0;
lolz.f.s = dis[x][i];
lolz.s = x;
pq.push(lolz);
dis2[x][i].f = 0;
dis2[x][i].s = dis[x][i];
while(!pq.empty()){
pair<pll,ll> p = pq.top();
pq.pop();
for(auto y:adj[p.s]){
if(dis2[y.to][i] > mp(dis2[p.s][i].f + y.cst,min(dis[y.to][i],dis2[p.s][i].s))){
dis2[y.to][i] = mp(dis2[p.s][i].f + y.cst,min(dis[y.to][i],dis2[p.s][i].s));
pq.push(mp(mp(dis2[y.to][i].f,dis2[y.to][i].s),y.to));
//pq.push(mp(dis2[y.to][i].f,mp(dis2[y.to][i].s,y.to)));
}
}
}
}
void solve(){
cin >> n >> m >> s >> t >> u >> v;
for(int i = 1;i <= m;i++){
ll x,y,c;
cin >> x >> y >> c;
adj[x].pb({y,c});
adj[y].pb({x,c});
}
for(int i = 1;i<=n;i++){
dis[i][0] = INF;
dis[i][1] = INF;
}
dijk(u);
dijk(v);
for(int i =1;i<=n;i++){
for(int j = 0;j<2;j++){
dis2[i][j].f = INF;
dis2[i][j].s = INF;
}
}
dijk2(s);
dijk2(t);
ll ans = INF;
pll k;k={INF,INF};
for(int i =1;i<=n;i++){
pll x = mp(dis2[i][0].f+dis2[i][1].f,dis2[i][0].s+dis2[i][1].s);
k=min(k,x);
}
ans = min(ans,min(k.s,dis[v][0]));
for(int i =1;i<=n;i++){
for(int j = 0;j<2;j++){
dis2[i][j].f = INF;
dis2[i][j].s = INF;
}
}
for(int i = 1;i<=n;i++){
dis[i][0] = INF;
dis[i][1] = INF;
}
swap(u,v);
dijk(u);
dijk(v);
dijk2(s);
dijk2(t);
for(int i =1;i<=n;i++){
pll x = mp(dis2[i][0].f+dis2[i][1].f,dis2[i][0].s+dis2[i][1].s);
k=min(k,x);
}
ans = min(ans,min(k.s,dis[v][0]));
cout << ans << endl;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
ll tt=1;
while(tt--){
solve();
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
737 ms |
23700 KB |
Output is correct |
2 |
Correct |
751 ms |
22124 KB |
Output is correct |
3 |
Correct |
726 ms |
23580 KB |
Output is correct |
4 |
Correct |
769 ms |
23836 KB |
Output is correct |
5 |
Correct |
643 ms |
21680 KB |
Output is correct |
6 |
Correct |
757 ms |
24092 KB |
Output is correct |
7 |
Correct |
751 ms |
22184 KB |
Output is correct |
8 |
Correct |
735 ms |
22184 KB |
Output is correct |
9 |
Correct |
668 ms |
21800 KB |
Output is correct |
10 |
Correct |
536 ms |
21476 KB |
Output is correct |
11 |
Correct |
215 ms |
13944 KB |
Output is correct |
12 |
Correct |
741 ms |
21840 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
793 ms |
22248 KB |
Output is correct |
2 |
Correct |
837 ms |
22076 KB |
Output is correct |
3 |
Correct |
810 ms |
21804 KB |
Output is correct |
4 |
Correct |
804 ms |
21924 KB |
Output is correct |
5 |
Correct |
793 ms |
22088 KB |
Output is correct |
6 |
Correct |
698 ms |
22412 KB |
Output is correct |
7 |
Correct |
890 ms |
22296 KB |
Output is correct |
8 |
Correct |
789 ms |
22360 KB |
Output is correct |
9 |
Correct |
780 ms |
22132 KB |
Output is correct |
10 |
Correct |
779 ms |
22056 KB |
Output is correct |
11 |
Correct |
213 ms |
14072 KB |
Output is correct |
12 |
Correct |
670 ms |
22256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
4608 KB |
Output is correct |
2 |
Correct |
7 ms |
2816 KB |
Output is correct |
3 |
Correct |
6 ms |
2816 KB |
Output is correct |
4 |
Correct |
25 ms |
6144 KB |
Output is correct |
5 |
Correct |
15 ms |
4424 KB |
Output is correct |
6 |
Correct |
7 ms |
2816 KB |
Output is correct |
7 |
Correct |
8 ms |
2944 KB |
Output is correct |
8 |
Correct |
8 ms |
2944 KB |
Output is correct |
9 |
Correct |
7 ms |
2688 KB |
Output is correct |
10 |
Correct |
15 ms |
4512 KB |
Output is correct |
11 |
Correct |
6 ms |
2816 KB |
Output is correct |
12 |
Correct |
6 ms |
2688 KB |
Output is correct |
13 |
Correct |
7 ms |
2816 KB |
Output is correct |
14 |
Correct |
7 ms |
2816 KB |
Output is correct |
15 |
Correct |
7 ms |
2816 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
737 ms |
23700 KB |
Output is correct |
2 |
Correct |
751 ms |
22124 KB |
Output is correct |
3 |
Correct |
726 ms |
23580 KB |
Output is correct |
4 |
Correct |
769 ms |
23836 KB |
Output is correct |
5 |
Correct |
643 ms |
21680 KB |
Output is correct |
6 |
Correct |
757 ms |
24092 KB |
Output is correct |
7 |
Correct |
751 ms |
22184 KB |
Output is correct |
8 |
Correct |
735 ms |
22184 KB |
Output is correct |
9 |
Correct |
668 ms |
21800 KB |
Output is correct |
10 |
Correct |
536 ms |
21476 KB |
Output is correct |
11 |
Correct |
215 ms |
13944 KB |
Output is correct |
12 |
Correct |
741 ms |
21840 KB |
Output is correct |
13 |
Correct |
793 ms |
22248 KB |
Output is correct |
14 |
Correct |
837 ms |
22076 KB |
Output is correct |
15 |
Correct |
810 ms |
21804 KB |
Output is correct |
16 |
Correct |
804 ms |
21924 KB |
Output is correct |
17 |
Correct |
793 ms |
22088 KB |
Output is correct |
18 |
Correct |
698 ms |
22412 KB |
Output is correct |
19 |
Correct |
890 ms |
22296 KB |
Output is correct |
20 |
Correct |
789 ms |
22360 KB |
Output is correct |
21 |
Correct |
780 ms |
22132 KB |
Output is correct |
22 |
Correct |
779 ms |
22056 KB |
Output is correct |
23 |
Correct |
213 ms |
14072 KB |
Output is correct |
24 |
Correct |
670 ms |
22256 KB |
Output is correct |
25 |
Correct |
19 ms |
4608 KB |
Output is correct |
26 |
Correct |
7 ms |
2816 KB |
Output is correct |
27 |
Correct |
6 ms |
2816 KB |
Output is correct |
28 |
Correct |
25 ms |
6144 KB |
Output is correct |
29 |
Correct |
15 ms |
4424 KB |
Output is correct |
30 |
Correct |
7 ms |
2816 KB |
Output is correct |
31 |
Correct |
8 ms |
2944 KB |
Output is correct |
32 |
Correct |
8 ms |
2944 KB |
Output is correct |
33 |
Correct |
7 ms |
2688 KB |
Output is correct |
34 |
Correct |
15 ms |
4512 KB |
Output is correct |
35 |
Correct |
6 ms |
2816 KB |
Output is correct |
36 |
Correct |
6 ms |
2688 KB |
Output is correct |
37 |
Correct |
7 ms |
2816 KB |
Output is correct |
38 |
Correct |
7 ms |
2816 KB |
Output is correct |
39 |
Correct |
7 ms |
2816 KB |
Output is correct |
40 |
Correct |
627 ms |
23948 KB |
Output is correct |
41 |
Correct |
638 ms |
22132 KB |
Output is correct |
42 |
Correct |
622 ms |
22076 KB |
Output is correct |
43 |
Correct |
203 ms |
14116 KB |
Output is correct |
44 |
Correct |
201 ms |
14072 KB |
Output is correct |
45 |
Correct |
597 ms |
21696 KB |
Output is correct |
46 |
Correct |
552 ms |
21704 KB |
Output is correct |
47 |
Correct |
665 ms |
23812 KB |
Output is correct |
48 |
Correct |
300 ms |
14012 KB |
Output is correct |
49 |
Correct |
512 ms |
23688 KB |
Output is correct |
50 |
Correct |
612 ms |
21952 KB |
Output is correct |
51 |
Correct |
555 ms |
21544 KB |
Output is correct |