이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define PI 3.1415926535
#define pb push_back
#define all(x) x.begin(), x.end()
const int N = 1e6+100, M = 1e5+10, K = 20;
const ll LMX = 1e16;
int n, m, s, t, x, y;
ll dx[N], dy[N], d[N], minx[N], miny[N];
vector<array<ll, 3>> g[N];
vector<bool> vis;
void solve(){
cin >> n >> m >> s >> t >> x >> y;
for(int i = 0; i < m; ++i){
int u, v, w; cin >> u >> v >> w;
g[u].pb({v, w, i});
g[v].pb({u, w, i});
}
vis.resize(n + 1);
//first dijkstra
priority_queue<pair<ll, int>> q;
q.push({0, x});
for(int i = 1; i <= n; ++i) dx[i] = i == x ? 0 : LMX;
for(int i = 1; i <= n; ++i) dy[i] = i == y ? 0 : LMX;
for(int i = 1; i <= n; ++i) d[i] = i == s ? 0 : LMX;
for(int i = 1; i <= n; ++i) minx[i] = LMX;
for(int i = 1; i <= n; ++i) miny[i] = LMX;
dx[0] = 0;
while(!q.empty()){
int v = q.top().second; q.pop();
if(vis[v]) continue;
vis[v] = 1;
for(auto U: g[v]){
int u = U[0], w = U[1];
if(!vis[u] && dx[u] > dx[v] + w){
dx[u] = dx[v] + w;
q.push({-dx[u], u});
}
}
}
fill(all(vis), 0);
q.push({0, y});
dy[0] = 0;
while(!q.empty()){
int v = q.top().second; q.pop();
if(vis[v]) continue;
vis[v] = 1;
for(auto U: g[v]){
int u = U[0], w = U[1];
if(!vis[u] && dy[u] > dy[v] + w){
dy[u] = dy[v] + w;
q.push({-dy[u], u});
}
}
}
priority_queue<array<ll, 2>> Q; // dist, node, min_x_dist
Q.push({0, s});
d[s] = 0;
fill(all(vis), 0);
while(!Q.empty()){
int v = Q.top()[1];
Q.pop();
if(vis[v]) continue;
minx[v] = dx[v];
miny[v] = dy[v];
vis[v] = 1;
for(auto U: g[v]){
int u = U[0], w = U[1];
if(vis[u] && d[v] == d[u] + w){
minx[v] = min(minx[u], minx[v]);
miny[v] = min(miny[u], miny[v]);
}
if(!vis[u] && d[u] > d[v] + w){
d[u] = d[v] + w;
Q.push({-d[u], u});
}
}
}
ll ans = LMX;
queue<int> qu; qu.push(t);
fill(all(vis), 0);
vis[t] = 1;
while(!qu.empty()){
int v = qu.front();
qu.pop();
ans = min(ans, minx[v] + dy[v]);
ans = min(ans, miny[v] + dx[v]);
for(auto U: g[v]){
int u = U[0], w = U[1];
if(d[u] == d[v] - w){
if(!vis[u]){
vis[u] = 1;
qu.push(u);
}
}
}
}
for(int i = 1; i <= n; ++i) ans = min(ans, dx[i] + dy[i]);
cout << ans;
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
int T = 1, aa;
// cin >> T;aa=T;
while(T--){
// cout << "Case #" << aa-T << ": ";
solve();
cout << '\n';
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:123:14: warning: unused variable 'aa' [-Wunused-variable]
123 | int T = 1, aa;
| ^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |