이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*
Author: Vo Minh Long
Codeforces: mncuchiinhuttt
CBT '25
*/
#include <iostream>
#include <stdio.h>
#include <time.h>
#include <string.h>
#include <assert.h>
#include <math.h>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <unordered_map>
#include <numeric>
#include <functional>
#include <bitset>
#include <unordered_set>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define long long long
#define FastIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define yuri ios::sync_with_stdio(0);
#define is cin.tie(0);
#define dabet cout.tie(0);
#define showTime() cerr << '\n' << "Running time: " << (1.0 * clock() / CLOCKS_PER_SEC) << "s\n";
#define NAME "zha"
#define len(a) (int)(a.size())
#define all(a) (a).begin(), (a).end()
const int N = 1e5 + 7;
const int BASE = 307;
const int INT_inf = 2e9;
const long LL_inf = 9e18;
const double eps = 1e-6;
const short dx[] = {1, 0, -1, 0};
const short dy[] = {0, 1, 0, -1};
const pair<long, long> MOD = {1e9 + 7, 998244353};
template<typename T1, typename T2> bool maximize(T1& a, T2 b){if(a < b) return a = b, 1; return 0;}
template<typename T1, typename T2> bool minimize(T1& a, T2 b){if(a > b) return a = b, 1; return 0;}
template<typename T1> T1 abs(T1 a){return a < 0 ? -a : a;}
template<typename T1> T1 sqr(T1 a){ return a * a; }
inline int readInt() { char c; int ans = 0; while ((c = getchar()) < '0' or c > '9'); ans = c - '0'; while ((c = getchar()) >= '0' and c <= '9') ans = ans * 10 + c - '0'; return ans; }
inline long readLong() { char c; long ans = 0; while ((c = getchar()) < '0' or c > '9'); ans = c - '0'; while ((c = getchar()) >= '0' and c <= '9') ans = ans * 10 + c - '0'; return ans; }
inline string readString() { string ans = ""; char c; while ((c = getchar()) < 33); ans.push_back(c); while ((c = getchar()) >= 33) ans.push_back(c); return ans; }
int n, m, s, t, s1, t1;
vector<pair<int, int> > adj[N];
void setData();
void solve();
int main()
{
setData();
solve();
}
void setData()
{
yuri is dabet
if (fopen(NAME".INP", "r"))
freopen(NAME".INP", "r", stdin),
freopen(NAME".OUT", "w", stdout);
scanf("%d%d%d%d%d%d", &n, &m, &s, &t, &s1, &t1);
for (int i = 1; i <= m; ++i)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
}
void solve()
{
priority_queue<array<long, 3> > q;
vector<vector<long> > dist(n + 1, vector<long>(2, 1e18));
q.push({dist[s1][0] = 0, s1, 0});
q.push({dist[t1][1] = 0, t1, 1});
while (!q.empty())
{
array<long, 3> u = q.top();
q.pop();
u[0] = -u[0];
if (u[0] != dist[u[1]][u[2]])
continue;
for (const pair<int, int>& v : adj[u[1]])
if (minimize(dist[v.first][u[2]], dist[u[1]][u[2]] + v.second))
q.push({-dist[v.first][u[2]], v.first, u[2]});
}
long answer = dist[t1][0];
vector<long> d(n + 1, 1e18);
function<void(int, int)> find = [&] (const int& begin, const int& end) {
vector<vector<long> > dp(n + 1, vector<long>(2, 1e18));
vector<bool> vis(n + 1, false);
priority_queue<array<long, 3> > q;
q.push({0, begin, 0});
while (!q.empty())
{
array<long, 3> u = q.top();
q.pop();
u[0] = -u[0];
if (vis[u[1]] == false)
{
vis[u[1]] = true;
d[u[1]] = u[0];
dp[u[1]][0] = min(dist[u[1]][0], dp[u[2]][0]);
dp[u[1]][1] = min(dist[u[1]][1], dp[u[2]][1]);
for (const pair<int, int>& v : adj[u[1]])
q.push({-u[0] - v.second, v.first, u[1]});
}
else if (u[0] == d[u[1]] and min(dist[u[1]][0], dp[u[2]][0]) + min(dist[u[1]][1], dp[u[2]][1]) <= dp[u[1]][0] + dp[u[1]][1])
{
dp[u[1]][0] = min(dist[u[1]][0], dp[u[2]][0]);
dp[u[1]][1] = min(dist[u[1]][1], dp[u[2]][1]);
}
}
minimize(answer, dp[end][0] + dp[end][1]);
};
find(s, t);
find(t, s);
printf("%lld\n", answer);
}
/* Some notes:
*/
컴파일 시 표준 에러 (stderr) 메시지
commuter_pass.cpp: In function 'void setData()':
commuter_pass.cpp:78:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
78 | freopen(NAME".INP", "r", stdin),
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:79:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
79 | freopen(NAME".OUT", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:80:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
80 | scanf("%d%d%d%d%d%d", &n, &m, &s, &t, &s1, &t1);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:84:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
84 | scanf("%d%d%d", &u, &v, &w);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
# | 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... |