結果
| 問題 | No.2569 はじめてのおつかいHard |
| ユーザー |
 あべし
|
| 提出日時 | 2023-12-02 16:29:14 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 225 ms / 2,000 ms |
| コード長 | 6,300 bytes |
| コンパイル時間 | 2,369 ms |
| コンパイル使用メモリ | 206,164 KB |
| 最終ジャッジ日時 | 2025-02-18 05:27:41 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 10 |
ソースコード
#include<bits/stdc++.h>
using namespace std;
// macro
#define rep(i, N) for(ll i = 0; i < (ll)(N); ++i)
#define per(i, N) for(ll i = (ll)(N) - 1; i >= 0; --i)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define bit(n, k) (((n) >> (k)) & 1)
#define pcnt(n) (bitset<64>(n).count())
#define endl '\n'
#define fi first
#define se second
#define mkpr make_pair
#define mktpl make_tuple
#define eb emplace_back
// input/output
template<class T> istream& operator>>(istream& is, vector<T>& V){
for(auto& it : V) is >> it;
return is;
}
template<class T> ostream& operator<<(ostream& os, vector<T>& V){
for(int i = 0; i < (int)V.size(); i++){
os << V[i];
os << (i + 1 != (int)V.size() ? " " : "");
}
return os;
}
template<class T1, class T2> istream& operator>>(istream& is, pair<T1, T2>& P){
is >> P.first >> P.second;
return is;
}
template<class T1, class T2> ostream& operator<<(ostream& os, pair<T1, T2> P){
os << P.first << " " << P.second << "";
return os;
}
// setup
void set_fast_ios(size_t precision){
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
cout << fixed << setprecision(precision);
cerr << fixed << setprecision(precision);
}
// make_vector
template <class T>
vector<T> make_vector(size_t a, T b) {
return vector<T>(a, b);
}
template <class... Ts>
auto make_vector(size_t a, Ts... ts) {
return vector<decltype(make_vector(ts...))>(a, make_vector(ts...));
}
// debug
#ifdef LOCAL
#define debug(x) cerr << "line"<< __LINE__ << ": " << #x << " = " << x << '\n'
#define debugln() cerr << "line" << __LINE__ << ": passed.\n"
#else
#define debug(x, ...) void(0)
#define debugln() void(0)
#endif
// type
using ll = long long;
using ull = unsigned long long;
using ld = double;
using i128 = __int128_t;
using State = string::iterator;
using Pair = pair<ll, ll>;
using Tuple = tuple<ll, ll, ll>;
template<class T> using max_heap = priority_queue<T>;
template<class T> using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<class T> using vec = vector<T>;
template<class T> using vvec = vec<vec<T>>;
template<class T> using vvvec = vec<vvec<T>>;
// constant
constexpr ll INF = 1001001001;
constexpr ll LINF = 1001001001001001001ll;
constexpr ll MOD998 = 998244353;
constexpr ll MOD107 = (ll)(1e9+7);
constexpr ll NIL = -1;
constexpr ll pm[2] = {1, -1};
constexpr ll dy[4] = {0, 1, 0, -1};
constexpr ll dx[4] = {1, 0, -1, 0};
constexpr ll dy8[8] = {0, 1, 1, 1, 0, -1, -1, -1};
constexpr ll dx8[8] = {1, 1, 0, -1, -1, -1, 0, 1};
// function
ll Gcd(ll a, ll b){ return b ? Gcd(b, a % b) : abs(a);}
ll Lcm(ll a, ll b){ return a / Gcd(a, b) * b;}
template<class T> T powi(T x, ll exp){
return exp > 0 ? (exp & 1 ? x : 1) * powi(x * x, exp >> 1) : x / x;
}
ll modpow(ll x, ll exp, ll mod){
x %= mod;
return exp > 0 ? (exp & 1 ? x : 1) * modpow(x * x, exp >> 1, mod) % mod : 1;
}
template<class T> bool chmin(T &a, T b){ return a > b ? (a = b, true) : 0;}
template<class T> bool chmax(T &a, T b){ return a < b ? (a = b, true) : 0;}
// modint
template <int mod> struct modint{
long long x;
modint() : x(0) {}
modint(long long _x){ x = _x % mod; if(x < 0) x += mod; }
constexpr modint operator-() const { return modint(-x); }
constexpr modint& operator+=(const modint& a){ if ((x += a.x) >= mod) x -= mod; return *this; }
constexpr modint& operator-=(const modint& a){ if ((x += mod - a.x) >= mod) x -= mod; return *this; }
constexpr modint& operator*=(const modint& a){ (x *= a.x) %= mod; return *this; }
constexpr modint& operator/=(const modint& a){ return (*this) *= a.mpow(mod-2); }
constexpr modint operator+(const modint& a) const { return modint(*this) += a; }
constexpr modint operator-(const modint& a) const { return modint(*this) -= a; }
constexpr modint operator*(const modint& a) const { return modint(*this) *= a; }
constexpr modint operator/(const modint& a) const { return modint(*this) /= a; }
constexpr bool operator==(const modint& a) const { return (*this).x == a.x; }
constexpr bool operator!=(const modint& a) const { return (*this).x != a.x; }
constexpr const modint mpow(long long exp) const {
modint res(1), x = *this;
for(; exp; exp >>= 1){
if(exp & 1) res *= x;
x *= x;
}
return res;
}
friend istream& operator>>(istream& is, modint& m){ is >> m.x; m = modint<mod>(m.x); return is; }
friend ostream& operator<<(ostream& os, const modint& m){ os << m.x; return os; }
bool operator<(const modint& a) const { return (*this).x < a.x; }
};
constexpr ll MOD = MOD998;
using mint = modint<MOD>;
template<class T> struct Dijkstra{
using DS = pair<T, int>;
int N;
T INFTY = 1001001001001001001ll;
vector<T> dist;
vector<int> prev;
priority_queue<DS, vector<DS>, greater<DS>> Que;
vector<vector<DS>> G;
Dijkstra(int N) : N(N), G(N), dist(N), prev(N) {}
void add_edge(int from, int to, T cst){
G[from].emplace_back(DS{cst, to});
}
void solve(int s){
for(int i = 0; i < N; i++) dist[i] = INFTY, prev[i] = -1;
dist[s] = 0, prev[s] = -1;
Que.push(DS{0, s});
while(!Que.empty()){
DS p = Que.top();
Que.pop();
int u = p.second;
if(dist[u] != p.first) continue;
for(auto v : G[u]){
if(dist[v.second] > dist[u] + v.first){
dist[v.second] = dist[u] + v.first;
prev[v.second] = u;
Que.push(DS{dist[v.second], v.second});
}
}
}
}
};
int main(){
set_fast_ios(15);
int N, M; cin >> N >> M;
Dijkstra<ll> DS(N), inv(N);
rep(i, M){
int u, v, t; cin >> u >> v >> t; u--, v--;
DS.add_edge(u, v, t);
inv.add_edge(v, u, t);
}
DS.solve(N - 2);
auto disA = DS.dist;
DS.solve(N - 1);
auto disB = DS.dist;
inv.solve(N - 2);
auto invA = inv.dist;
inv.solve(N - 1);
auto invB = inv.dist;
rep(i, N - 2){
ll ans = LINF;
chmin(ans, invA[i] + disA[N - 1] + disB[i]);
chmin(ans, invB[i] + disB[N - 2] + disA[i]);
cout << (ans < LINF ? ans : -1) << endl;
}
}