#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fi first
#define se second
const int N = 2e6 + 7;
const ll INF = 1e18;
int node, edge, trace[N], par[N], s, t, n, m;
vector<pll> adj[N];
queue<int> q;
bool vst[N];
ll dp[N];
// void run_with_file(){
// if(fopen(file".inp", "r")){
// freopen(file".inp", "r", stdin);
// freopen(file".out", "w", stdout);
// }
// }
void inp(){
cin >> node >> edge;
cin >> s >> t;
cin >> n >> m;
for(int i = 1; i <= edge; ++i){
int u, v;
ll w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
}
void dijkstra(int x){
vector<ll> d(node + 1, INF);
d[x] = 0;
priority_queue<pll, vector<pll>, greater<pll>> Q;
Q.push({d[x], x});
while(!Q.empty()){
pll top = Q.top(); Q.pop();
int u = top.se;
ll kc = top.fi;
if(d[u] < kc) continue;
for(auto it : adj[u]){
int v = it.fi;
ll w = it.se;
if(d[v] > kc + w){
d[v] = kc + w;
trace[v] = u;
Q.push({d[v], v});
}
}
}
while(t != x){
par[t] = trace[t];
t = trace[t];
}
}
void bfs(int x){
vst[x] = true;
q.push(x);
while(!q.empty()){
int u = q.front(); q.pop();
for(auto it : adj[u]){
int v = it.fi;
ll w = it.se;
if(!vst[v]){
q.push(v);
vst[v] = true;
dp[v] = dp[u] + w * (par[v] != u ? 1 : 0);
}
else{
dp[v] = min(dp[v], dp[u] + w * (par[v] != u ? 1 : 0));
}
}
}
}
int main(){
cin.tie(0)->sync_with_stdio(0);
// run_with_file();
inp();
dijkstra(s);
bfs(n);
cout << dp[m];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
129 ms |
68840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
156 ms |
68948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
55644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
129 ms |
68840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
