#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAX_N = 100000;
int n, s, t, u, v, D[MAX_N][2];
vector<vector<int>>parent(MAX_N);
vector<pair<int,int>>dp(MAX_N), M(MAX_N);
vector<vector<pair<int,int>>>adjL(MAX_N);
void calc(int x, int type) {
priority_queue<pair<int,int>>pq;
pq.push({0, x});
for(int i=0; i<n; ++i) D[i][type] = -1;
D[x][type] = 0;
while(!pq.empty()) {
int cur = pq.top().second;
pq.pop();
for(pair<int,int>adj: adjL[cur]) {
int w = adj.second + D[cur][type];
if(D[adj.first][type] == -1) {
D[adj.first][type] = w;
pq.push({-w, adj.first});
}
}
}
}
pair<int,int> func(int pos) {
if(dp[pos].first != -1) return dp[pos];
dp[pos].first = M[pos].first = D[pos][0];
dp[pos].second = M[pos].second = D[pos][1];
for(int p: parent[pos]) {
pair<int,int>cnt = func(p);
M[pos].first = min(M[pos].first, M[p].first);
M[pos].second = min(M[pos].second, M[p].second);
if(cnt.first + cnt.second < dp[pos].first + dp[pos].second) dp[pos].first = cnt.first, dp[pos].second = cnt.second;
}
if(M[pos].first + D[pos][1] < dp[pos].first + dp[pos].second) dp[pos].first = M[pos].first;
if(M[pos].second + D[pos][0] < dp[pos].first + dp[pos].second) dp[pos].second = M[pos].second;
return dp[pos];
}
void solve() {
int m;
cin >> n >> m >> s >> t >> u >> v;
--s, --t, --u, --v;
for(int i=0; i<m; ++i) {
int a, b, w;
cin >> a >> b >> w;
--a, --b;
adjL[a].push_back({b, w});
adjL[b].push_back({a, w});
}
for(int i=0; i<n; ++i) dp[i] = {-1, -1};
priority_queue<pair<int,int>>pq;
pq.push({0, s});
vector<int>d(n, -1);
d[s] = 0;
while(!pq.empty()) {
int dist = -pq.top().first, cur = pq.top().second;
pq.pop();
for(pair<int,int>adj: adjL[cur]) {
int w = dist + adj.second;
if(d[adj.first] == -1) {
pq.push({-w, adj.first});
d[adj.first] = w;
parent[adj.first].push_back(cur);
} else if(w == d[adj.first]) parent[adj.first].push_back(cur);
}
}
calc(u, 0);
calc(v, 1);
func(t);
cout << min(dp[t].first + dp[t].second, min(D[u][1], D[v][0])) << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//freopen("shortcut.in", "r", stdin);
//freopen("shortcut.out", "w", stdout);
int t=1;
while(t--) solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
158 ms |
29960 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
196 ms |
29636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
10076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
158 ms |
29960 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
