이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define ld long double
#define vv vector
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define mod 1000000007
typedef pair<ll, ll> pll;
typedef vv<ll> vll;
typedef vv<ld> vld;
typedef vv<pll> vpll;
typedef set<ll>::iterator sitr;
#define fastio \
ios_base::sync_with_stdio(0); \
cin.tie(0);
///////////////////////////////////
ll inf = 1e17;
void dijkstra(ll node, vll &dist, vv<vpll> &g)
{
priority_queue<pll, vpll, greater<pll>> mh;
mh.push({0, node});
while (!mh.empty())
{
pll t = mh.top();
mh.pop();
if (dist[t.S] != inf)
continue;
dist[t.S] = t.F;
for (ll i = 0; i < g[t.S].size(); i++)
mh.push({t.F + g[t.S][i].S, g[t.S][i].F});
}
}
void dfs(ll node, vll &dist1, vll &dist2, vll &vis, vv<vpll> &g, vll &top_sort, vv<vll> &valid_child_g, vv<vll> &valid_par_g, ll t)
{
if (vis[node])
return;
vis[node] = 1;
for (ll i = 0; i < g[node].size(); i++)
{
if (dist1[node] + g[node][i].S + dist2[g[node][i].F] == dist1[t])
{
dfs(g[node][i].F, dist1, dist2, vis, g, top_sort, valid_child_g, valid_par_g, t);
valid_child_g[node].pb(g[node][i].F);
valid_par_g[g[node][i].F].pb(node);
}
}
top_sort.pb(node);
}
int main()
{
fastio;
ll T = 1;
// cin >> T;
while (T--)
{
ll i, j, a, b, c, n, m, u, v, s, t, node;
cin >> n >> m;
cin >> s >> t;
cin >> u >> v;
vv<vpll> g(n + 1);
vv<vll> valid_child_g(n + 1), valid_par_g(n + 1);
for (i = 0; i < m; i++)
{
cin >> a >> b >> c;
g[a].pb({b, c});
g[b].pb({a, c});
}
vll dS(n + 1, inf), dU(n + 1, inf), dV(n + 1, inf), dT(n + 1, inf);
dijkstra(s, dS, g);
dijkstra(u, dU, g);
dijkstra(v, dV, g);
dijkstra(t, dT, g);
vll vis(n + 1, 0), top_sort;
dfs(s, dS, dT, vis, g, top_sort, valid_child_g, valid_par_g, t);
reverse(top_sort.begin(), top_sort.end());
// for (i = 1; i <= n; i++)
// {
// cout << i << ": ";
// for (j = 0; j < valid_child_g[i].size(); j++)
// cout << valid_child_g[i][j] << " ";
// cout << endl;
// }
// for (i = 1; i <= n; i++)
// {
// cout << i << ": ";
// for (j = 0; j < valid_par_g[i].size(); j++)
// cout << valid_par_g[i][j] << " ";
// cout << endl;
// }
vll dp_child(n + 1, inf), dp_ancestor(n + 1, inf);
for (i = top_sort.size() - 1; i >= 0; i--)
{
node = top_sort[i];
dp_child[node] = dV[node];
for (j = 0; j < valid_child_g[node].size(); j++)
dp_child[node] = min(dp_child[node], dp_child[valid_child_g[node][j]]);
}
for (i = 0; i < top_sort.size(); i++)
{
node = top_sort[i];
dp_ancestor[node] = dV[node];
for (j = 0; j < valid_par_g[node].size(); j++)
dp_ancestor[node] = min(dp_ancestor[node], dp_ancestor[valid_par_g[node][j]]);
}
// //
// cout << endl;
// for (i = 1; i <= n; i++)
// cout << dS[i] << " " << dU[i] << " " << dV[i] << " " << dT[i] << endl;
// cout << endl;
// for (auto i : top_sort)
// cout << i << " ";
// cout << endl;
// for (i = 1; i <= n; i++)
// cout << dp_child[i] << " ";
// cout << endl;
// for (i = 1; i <= n; i++)
// cout << dp_ancestor[i] << " ";
// cout << endl;
// //
ll ans = dU[v];
for (i = 0; i < top_sort.size(); i++)
ans = min({ans, dU[top_sort[i]] + dp_child[top_sort[i]],
dU[top_sort[i]] + dp_ancestor[top_sort[i]]});
cout << ans << endl;
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
commuter_pass.cpp: In function 'void dijkstra(long long int, vll&, std::vector<std::vector<std::pair<long long int, long long int> > >&)':
commuter_pass.cpp:38:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for (ll i = 0; i < g[t.S].size(); i++)
| ~~^~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void dfs(long long int, vll&, vll&, vll&, std::vector<std::vector<std::pair<long long int, long long int> > >&, vll&, std::vector<std::vector<long long int> >&, std::vector<std::vector<long long int> >&, long long int)':
commuter_pass.cpp:48:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for (ll i = 0; i < g[node].size(); i++)
| ~~^~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:112:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | for (j = 0; j < valid_child_g[node].size(); j++)
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:116:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
116 | for (i = 0; i < top_sort.size(); i++)
| ~~^~~~~~~~~~~~~~~~~
commuter_pass.cpp:120:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
120 | for (j = 0; j < valid_par_g[node].size(); j++)
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:143:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
143 | for (i = 0; i < top_sort.size(); i++)
| ~~^~~~~~~~~~~~~~~~~
# | 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... |