#include <bits/stdc++.h>
using namespace std;
const long long oo = 1e18;
const int MAXN = 1e5 + 7;
vector<pair<int, int>> G[MAXN];
long long cost[MAXN][4];
int layer[MAXN];
bool visited[MAXN];
int n;
void preprocces(int a, int b){
vector<long long> costd(n+1, oo);
vector<int> D[MAXN];
priority_queue<tuple<long long, int, int>> Q;
Q.push({0, a, 0});
while(Q.size()){
auto [d, v, p] = Q.top();
Q.pop();
if(costd[v] < -d) continue;
else if(costd[v] == -d){
if(p != 0) D[v].push_back(p);
continue;
}
D[v].clear();
D[v].shrink_to_fit();
costd[v] = -d;
if(p != 0) D[v].push_back(p);
for(auto [u, c] : G[v]){
if(costd[u] < costd[v] + c) continue;
else if(costd[u] == costd[v] + c){
D[u].push_back(v);
continue;
}
Q.push({-(costd[v] + c), u, v});
}
}
queue<int> W;
W.push(b);
layer[b] = 1;
visited[b] = 1;
while(W.size()){
int xd = W.front(); W.pop();
for(auto x : D[xd]){
if(visited[x]) continue;
layer[x] = layer[xd] + 1;
W.push(x);
visited[x] = 1;
}
}
/*
for(int i = 1; i <= n; i++)
if(layer[i]) cout << "v: " << i << " layer: " << layer[i] << endl;
*/
}
void dijkstra(int a){
// stan 0 jeszcze nie weszlismy na sciezke pass'a
// stan 1 weszlismy na sciezke pass'a ale idziemy w gore
// stan 2 weszlismy na sciezka pass'a ale idziemy w dol
// stan 3 wyszlismy z sciezki pass'a
priority_queue<tuple<long long, int, int>> Q;
Q.push({0, a, 0});
while(Q.size()){
auto [d, v, s] = Q.top(); Q.pop();
if(cost[v][s] <= -d) continue;
cost[v][s] = -d;
if(s == 0 && layer[v]){
if(cost[v][1] > -d) Q.push({-d, v, 1});
if(cost[v][2] > -d) Q.push({-d, v, 2});
}
else if(s == 1 || s == 2){
if(cost[v][3] > -d) Q.push({-d, v, 3});
}
for(auto [u, c] : G[v]){
if(s == 0 || s == 3){
if(cost[u][s] <= cost[v][s] + c) continue;
Q.push({-(cost[v][s] + c), u, s});
}
else if(s == 1){
if(layer[u] <= layer[v] || !layer[u]) continue;
if(cost[u][s] <= cost[v][s]) continue;
Q.push({-cost[v][s], u, s});
}
else if(s == 2){
if(layer[u] >= layer[v] || !layer[u]) continue;
if(cost[u][s] <= cost[v][s]) continue;
Q.push({-cost[v][s], u, s});
}
}
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int m, s, t, u, v;
cin >> n >> m >> s >> t >> u >> v;
for(int i = 1; i <= m; i++){
int a, b, c;
cin >> a >> b >> c;
G[a].push_back({b, c});
G[b].push_back({a, c});
}
preprocces(s, t);
for(int i = 1; i <= n; i++)
cost[i][0] = cost[i][1] = cost[i][2] = cost[i][3] = oo;
dijkstra(u);
cout << min({cost[v][0], cost[v][1], cost[v][2], cost[v][3]}) << "\n";
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
195 ms |
24120 KB |
Output is correct |
2 |
Execution timed out |
2063 ms |
20720 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
2009 ms |
19668 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
22 ms |
10012 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
195 ms |
24120 KB |
Output is correct |
2 |
Execution timed out |
2063 ms |
20720 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |