이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC optimize("Ofast")
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#ifdef ENABLE_DEBUG
#include <debug.h>
#else
#define DEBUG(...) do {} while (0)
#endif
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using ull = unsigned long long;
using lll = __int128;
using ulll = unsigned __int128;
using ld = long double;
template<typename T, size_t N> using ar = array<T, N>;
template<typename T, typename Cmp = less<T>>
using iset = tree<T, null_type, Cmp, rb_tree_tag,
tree_order_statistics_node_update, allocator<T>>;
#define REPSI(name, start, stop, step) for (ll name = start; name < (ll)stop; name += step)
#define REPS(name, start, stop) REPSI(name, start, stop, 1)
#define REP(name, stop) REPS(name, 0, stop)
#define RREPSI(name, start, stop, step) for (ll name = stop-1; name >= (ll)start; name -= step)
#define RREPS(name, start, stop) RREPSI(name, start, stop, 1)
#define RREP(name, stop) RREPS(name, 0, stop)
template<typename T> void cins(T &first) { cin >> first; }
template<typename T, typename... Ts> void cins(T &first, T &second, Ts&... rest) {
cin >> first;
cins(second, rest...);
}
#define GET(type, ...) type __VA_ARGS__; cins(__VA_ARGS__)
#define GETI(...) GET(int, __VA_ARGS__)
#define GETLL(...) GET(ll, __VA_ARGS__)
#define GETS(...) GET(string, __VA_ARGS__)
#define GETD(...) GET(double, __VA_ARGS__)
#define GETC(...) GET(char, __VA_ARGS__)
struct hsh {
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
x += FIXED_RANDOM;
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(ar<int, 2> a) const {
return hsh{}((ll(a[0])<<32) | a[1]);
}
};
const int mxN = 1e5;
vector<ar<ll, 4>> g[mxN];
vector<ll> dist[mxN];
gp_hash_table<ar<int, 2>, ll, hsh> cc;
int main() {
ios::sync_with_stdio(0);cin.tie(0);
GETI(n, m);
REP(mm, m) {
GETI(i, j, c, p); --i, --j;
ll oi = g[i].size();
ll oj = g[j].size();
g[i].push_back({j, c, p, oj});
g[j].push_back({i, c, p, oi});
cc[{i, c}] += p;
cc[{j, c}] += p;
}
REP(i, n) dist[i].resize(g[i].size()+1, -1);
// cost, i, j
priority_queue<ar<ll, 3>, vector<ar<ll, 3>>, greater<ar<ll, 3>>> pq;
pq.push({0, 0, g[0].size()});
while (pq.size()) {
auto [cost, i, j] = pq.top();
pq.pop();
if (dist[i][j] != -1) continue;
dist[i][j] = cost;
ll changed = -1;
if (j < g[i].size()) changed = g[i][j][1];
REP(k, g[i].size()) {
if (k == j) continue;
auto [nxt, color, w, nj] = g[i][k];
ll others = cc.find({i, color})->second-w;
if (color == changed)
others -= g[i][j][2];
if (dist[nxt][g[nxt].size()] == -1)
pq.push({cost+others, nxt, g[nxt].size()});
if (dist[nxt][nj] == -1)
pq.push({cost+w, nxt, nj});
}
}
REP(i, n) DEBUG(dist[i]);
ll ans = 1LL<<60;
for (ll x : dist[n-1]) if (x != -1) ans = min(ans, x);
if (ans == (1LL<<60)) ans = -1;
cout << ans << '\n';
}
컴파일 시 표준 에러 (stderr) 메시지
Main.cpp: In function 'int main()':
Main.cpp:94:27: warning: narrowing conversion of 'g[0].std::vector<std::array<long long int, 4> >::size()' from 'std::vector<std::array<long long int, 4> >::size_type' {aka 'long unsigned int'} to 'long long int' [-Wnarrowing]
94 | pq.push({0, 0, g[0].size()});
| ~~~~~~~~~^~
Main.cpp:104:11: warning: comparison of integer expressions of different signedness: 'std::tuple_element<2, std::array<long long int, 3> >::type' {aka 'long long int'} and 'std::vector<std::array<long long int, 4> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | if (j < g[i].size()) changed = g[i][j][1];
| ~~^~~~~~~~~~~~~
Main.cpp:110:28: warning: narrowing conversion of 'i' from 'std::tuple_element<1, std::array<long long int, 3> >::type' {aka 'long long int'} to 'int' [-Wnarrowing]
110 | ll others = cc.find({i, color})->second-w;
| ^
Main.cpp:110:31: warning: narrowing conversion of 'color' from 'std::tuple_element<1, std::array<long long int, 4> >::type' {aka 'long long int'} to 'int' [-Wnarrowing]
110 | ll others = cc.find({i, color})->second-w;
| ^~~~~
Main.cpp:116:47: warning: narrowing conversion of 'g[nxt].std::vector<std::array<long long int, 4> >::size()' from 'std::vector<std::array<long long int, 4> >::size_type' {aka 'long unsigned int'} to 'long long int' [-Wnarrowing]
116 | pq.push({cost+others, nxt, g[nxt].size()});
| ~~~~~~~~~~~^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |