이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
ifstream in("file.in");
#define make_arc(N, a, b); N.node = a; N.dist = b;
#define ll long long
const ll inf = 1LL * 1000 * 1000 * 1000 * 1000 * 1000 * 1000;
ll best = 0;
struct arc{
int node;
ll dist;
arc(){
node = 0; dist = 0;
}
};
bool rule(arc A, arc B)
{
if (A.dist == B.dist)
return A.node < B.node;
return A.dist < B.dist;
}
void Dijkstra(int start, vector<vector<int>> &Vec, vector<vector<int>> &Cost, vector<ll> &D)
{
D.assign(Cost.size(), inf);
D[start] = 0;
arc A; make_arc(A, start, 0);
set<arc, bool(*)(arc, arc)> Set(rule);
Set.insert(A);
while (!Set.empty())
{
auto X = *Set.begin();
Set.erase(X);
for (int i = 0; i < Vec[X.node].size(); i++)
{
int vecin = Vec[X.node][i];
if (D[X.node] + Cost[X.node][i] < D[vecin])
{
D[vecin] = D[X.node] + Cost[X.node][i];
make_arc(A, vecin, 0);
auto index = Set.lower_bound(A);
if (index != Set.end() && index->node == vecin)
Set.erase(index);
make_arc(A, vecin, D[vecin]);
Set.insert(A);
}
}
}
}
struct base{
ll f, s, sum;
base() {
f = s = sum = inf;
}
};
vector<bool> Been;
void TryRoutes(int node, int end, vector<vector<int>> &Vec, vector<vector<int>> &Cost, vector<vector<ll>> &Dist, vector<base> &Bsum)
{
Been[node] = true;
Bsum[node].f = Dist[2][node];
Bsum[node].s = Dist[3][node];
Bsum[node].sum = Bsum[node].f + Bsum[node].s;
ll Min1 = Bsum[node].f, Min2 = Bsum[node].s;
if (node == end)
return;
for (int i = 0; i < Vec[node].size(); i++)
{
int vecin = Vec[node][i];
if (Dist[0][node] + Cost[node][i] + Dist[1][vecin] != Dist[0][end])
continue;
if (Been[vecin] == false)
TryRoutes(vecin, end, Vec, Cost, Dist, Bsum);
Bsum[node].sum = min(Bsum[node].sum, Bsum[vecin].sum);
Min1 = min(Min1, Bsum[vecin].f);
Min2 = min(Min2, Bsum[vecin].s);
}
Bsum[node].sum = min(Bsum[node].sum, Bsum[node].f + Min2);
Bsum[node].sum = min(Bsum[node].sum, Bsum[node].s + Min1);
Bsum[node].f = min(Bsum[node].f, Min1);
Bsum[node].s = min(Bsum[node].s, Min2);
}
int main()
{
int n, m, S, T, U, V;
cin>> n >> m;
cin>> S >> T;
cin>> U >> V;
S--; T--; U--; V--;
vector<vector<int>> Vec(n), Cost(n);
for (int i = 0; i < m; i++)
{
int a, b, c;
cin>> a >> b >> c;
a--; b--;
Vec[a].push_back(b);
Vec[b].push_back(a);
Cost[a].push_back(c);
Cost[b].push_back(c);
}
vector<vector<ll>> Dist(4, vector<ll> (n));
Dijkstra(S, Vec, Cost, Dist[0]);
Dijkstra(T, Vec, Cost, Dist[1]);
Dijkstra(U, Vec, Cost, Dist[2]);
Dijkstra(V, Vec, Cost, Dist[3]);
//pentru usurinta S-0 T-1 U-2 V-3
best = Dist[2][V];
vector<base> Bsum(n);
Been.assign(n, false);
TryRoutes(S, T, Vec, Cost, Dist, Bsum);
best = min(best, Bsum[S].sum);
cout<< best;
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
commuter_pass.cpp: In function 'void Dijkstra(int, std::vector<std::vector<int> >&, std::vector<std::vector<int> >&, std::vector<long long int>&)':
commuter_pass.cpp:40:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for (int i = 0; i < Vec[X.node].size(); i++)
| ~~^~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void TryRoutes(int, int, std::vector<std::vector<int> >&, std::vector<std::vector<int> >&, std::vector<std::vector<long long int> >&, std::vector<base>&)':
commuter_pass.cpp:80:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for (int i = 0; i < Vec[node].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... |