結果
| 問題 | No.2739 Time is money |
| ユーザー |
 hotman78
|
| 提出日時 | 2024-04-20 10:21:42 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 225 ms / 2,000 ms |
| コード長 | 13,988 bytes |
| コンパイル時間 | 3,455 ms |
| コンパイル使用メモリ | 248,632 KB |
| 実行使用メモリ | 22,120 KB |
| 最終ジャッジ日時 | 2024-10-12 05:52:08 |
| 合計ジャッジ時間 | 9,459 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 18 |
ソースコード
// author: hotman78
// date: 2024/04/20-10:21:34
// --- begin raw code -----------------
// #include"cpplib/util/template.hpp"
// #include"cpplib/graph_tree/dijkstra.hpp"
//
// void solve(){
// lint n,m,x;
// cin>>n>>m>>x;
// graph_w<lint>v(n);
// rep(i,m){
// lint s,t,c,d;
// cin>>s>>t>>c>>d;
// s--;t--;
// v[s].push_back({t,d*x+c});
// v[t].push_back({s,d*x+c});
// }
// // 1円を1/x時間で稼ぐと考えると d+c/x で比較できる
// lint ans=dijkstra<lint>(v,0)[n-1];
// if(ans>=INF/2){cout<<-1<<endl;}
// else cout<<(ans+x-1)/x<<endl;
// }
//
// int main(){
// solve();
// // lint t;cin>>t;while(t--)solve();
// }
// --- end raw code -----------------
#line 2 "cpplib/util/template.hpp"
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
// #pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
#line 1 "cpplib/util/ioutil.hpp"
// template <class Head,class... Args>
// std::ostream& output(std::ostream& out,const Head& head,const Args&... args){
// out>>head;
// return output(head,args...);
// }
// template <class Head>
// std::ostream& output(std::ostream& out,const Head& head){
// out>>head;
// return out;
// }
template <typename T, typename E>
std::ostream &operator<<(std::ostream &out, std::pair<T, E> v) {
out << "(" << v.first << "," << v.second << ")";
return out;
}
// template <class... Args>
// ostream& operator<<(ostream& out,std::tuple<Args...>v){
// std::apply(output,v);
// return out;
// }
#line 11 "cpplib/util/template.hpp"
struct __INIT__ {
__INIT__() {
cin.tie(0);
ios::sync_with_stdio(false);
cout << fixed << setprecision(15);
}
} __INIT__;
typedef long long lint;
constexpr long long INF = 1LL << 60;
constexpr int IINF = 1 << 30;
constexpr double EPS = 1e-10;
#ifndef REACTIVE
#define endl '\n';
#endif
typedef vector<lint> vec;
typedef vector<vector<lint>> mat;
typedef vector<vector<vector<lint>>> mat3;
typedef vector<string> svec;
typedef vector<vector<string>> smat;
template <typename T> using V = vector<T>;
template <typename T> using VV = V<V<T>>;
#define output(t) \
{ \
bool f = 0; \
for (auto val : (t)) { \
cout << (f ? " " : "") << val; \
f = 1; \
} \
cout << endl; \
}
#define output2(t) \
{ \
for (auto i : t) \
output(i); \
}
#define debug(t) \
{ \
bool f = 0; \
for (auto i : t) { \
cerr << (f ? " " : "") << i; \
f = 1; \
} \
cerr << endl; \
}
#define debug2(t) \
{ \
for (auto i : t) \
debug(i); \
}
#define loop(n) for (long long _ = 0; _ < (long long)(n); ++_)
#define _overload4(_1, _2, _3, _4, name, ...) name
#define __rep(i, a) repi(i, 0, a, 1)
#define _rep(i, a, b) repi(i, a, b, 1)
#define repi(i, a, b, c) \
for (long long i = (long long)(a); i < (long long)(b); i += c)
#define rep(...) _overload4(__VA_ARGS__, repi, _rep, __rep)(__VA_ARGS__)
#define _overload3_rev(_1, _2, _3, name, ...) name
#define _rep_rev(i, a) repi_rev(i, 0, a)
#define repi_rev(i, a, b) \
for (long long i = (long long)(b)-1; i >= (long long)(a); --i)
#define rrep(...) _overload3_rev(__VA_ARGS__, repi_rev, _rep_rev)(__VA_ARGS__)
#define all(n) begin(n), end(n)
template <typename T, typename E> bool chmin(T &s, const E &t) {
bool res = s > t;
s = min<T>(s, t);
return res;
}
template <typename T, typename E> bool chmax(T &s, const E &t) {
bool res = s < t;
s = max<T>(s, t);
return res;
}
const vector<lint> dx = {1, 0, -1, 0, 1, 1, -1, -1};
const vector<lint> dy = {0, 1, 0, -1, 1, -1, 1, -1};
#define SUM(v) accumulate(all(v), 0LL)
#if __cplusplus >= 201703L
template <typename T, typename... Args>
auto make_vector(T x, int arg, Args... args) {
if constexpr (sizeof...(args) == 0)
return vector<T>(arg, x);
else
return vector(arg, make_vector<T>(x, args...));
}
#endif
#define bit(n, a) ((n >> a) & 1)
#define extrep(v, ...) for (auto v : make_mat_impl({__VA_ARGS__}))
vector<vector<long long>> make_mat_impl(vector<long long> v) {
if (v.empty())
return vector<vector<long long>>(1, vector<long long>());
long long n = v.back();
v.pop_back();
vector<vector<long long>> ret;
vector<vector<long long>> tmp = make_mat_impl(v);
for (auto e : tmp)
for (long long i = 0; i < n; ++i) {
ret.push_back(e);
ret.back().push_back(i);
}
return ret;
}
using graph = vector<vector<int>>;
template <typename T> using graph_w = vector<vector<pair<int, T>>>;
#if __cplusplus >= 201703L
constexpr inline long long powll(long long a, long long b) {
long long res = 1;
while (b--)
res *= a;
return res;
}
#endif
template <typename T, typename E>
pair<T, E> &operator+=(pair<T, E> &s, const pair<T, E> &t) {
s.first += t.first;
s.second += t.second;
return s;
}
template <typename T, typename E>
pair<T, E> &operator-=(pair<T, E> &s, const pair<T, E> &t) {
s.first -= t.first;
s.second -= t.second;
return s;
}
template <typename T, typename E>
pair<T, E> operator+(const pair<T, E> &s, const pair<T, E> &t) {
auto res = s;
return res += t;
}
template <typename T, typename E>
pair<T, E> operator-(const pair<T, E> &s, const pair<T, E> &t) {
auto res = s;
return res -= t;
}
#define BEGIN_STACK_EXTEND(size) \
void *stack_extend_memory_ = malloc(size); \
void *stack_extend_origin_memory_; \
char *stack_extend_dummy_memory_ = (char *)alloca( \
(1 + (int)(((long long)stack_extend_memory_) & 127)) * 16); \
*stack_extend_dummy_memory_ = 0; \
asm volatile("mov %%rsp, %%rbx\nmov %%rax, %%rsp" \
: "=b"(stack_extend_origin_memory_) \
: "a"((char *)stack_extend_memory_ + (size)-1024));
#define END_STACK_EXTEND \
asm volatile("mov %%rax, %%rsp" ::"a"(stack_extend_origin_memory_)); \
free(stack_extend_memory_);
int floor_pow(int n) { return n ? 31 - __builtin_clz(n) : 0; }
#line 5 "cpplib/graph_tree/graph_template.hpp"
/**
* @brief グラフテンプレート
*/
using graph = std::vector<std::vector<int>>;
template <typename T>
using graph_w = std::vector<std::vector<std::pair<int, T>>>;
graph load_graph(int n, int m) {
graph g(n);
for (int i = 0; i < m; ++i) {
int s, t;
std::cin >> s >> t;
--s;
--t;
g[s].push_back(t);
g[t].push_back(s);
}
return g;
}
graph load_digraph(int n, int m) {
graph g(n);
for (int i = 0; i < m; ++i) {
int s, t;
std::cin >> s >> t;
--s;
--t;
g[s].push_back(t);
}
return g;
}
graph load_graph0(int n, int m) {
graph g(n);
for (int i = 0; i < m; ++i) {
int s, t;
std::cin >> s >> t;
g[s].push_back(t);
g[t].push_back(s);
}
return g;
}
graph load_digraph0(int n, int m) {
graph g(n);
for (int i = 0; i < m; ++i) {
int s, t;
std::cin >> s >> t;
g[s].push_back(t);
}
return g;
}
graph load_tree(int n) {
graph g(n);
for (int i = 0; i < n - 1; ++i) {
int s, t;
std::cin >> s >> t;
--s;
--t;
g[s].push_back(t);
g[t].push_back(s);
}
return g;
}
graph load_tree0(int n) {
graph g(n);
for (int i = 0; i < n - 1; ++i) {
int s, t;
std::cin >> s >> t;
g[s].push_back(t);
g[t].push_back(s);
}
return g;
}
graph load_treep(int n) {
graph g(n);
for (int i = 0; i < n - 1; ++i) {
int t;
std::cin >> t;
g[i + 1].push_back(t);
g[t].push_back(i + 1);
}
return g;
}
template <typename T> graph_w<T> load_graph_weight(int n, int m) {
graph_w<T> g(n);
for (int i = 0; i < m; ++i) {
int s, t;
T u;
std::cin >> s >> t >> u;
--s;
--t;
g[s].emplace_back(t, u);
g[t].emplace_back(s, u);
}
return g;
}
template <typename T> graph_w<T> load_digraph_weight(int n, int m) {
graph_w<T> g(n);
for (int i = 0; i < m; ++i) {
int s, t;
T u;
std::cin >> s >> t >> u;
--s;
--t;
g[s].emplace_back(t, u);
}
return g;
}
template <typename T> graph_w<T> load_graph0_weight(int n, int m) {
graph_w<T> g(n);
for (int i = 0; i < m; ++i) {
int s, t;
T u;
std::cin >> s >> t >> u;
g[s].emplace_back(t, u);
g[t].emplace_back(s, u);
}
return g;
}
template <typename T> graph_w<T> load_digraph0_weight(int n, int m) {
graph_w<T> g(n);
for (int i = 0; i < m; ++i) {
int s, t;
T u;
std::cin >> s >> t >> u;
g[s].emplace_back(t, u);
}
return g;
}
template <typename T> graph_w<T> load_tree_weight(int n) {
graph_w<T> g(n);
for (int i = 0; i < n - 1; ++i) {
int s, t;
T u;
std::cin >> s >> t >> u;
--s;
--t;
g[s].emplace_back(t, u);
g[t].emplace_back(s, u);
}
return g;
}
template <typename T> graph_w<T> load_tree0_weight(int n) {
graph_w<T> g(n);
for (int i = 0; i < n - 1; ++i) {
int s, t;
T u;
std::cin >> s >> t >> u;
g[s].emplace_back(t, u);
g[t].emplace_back(s, u);
}
return g;
}
template <typename T> graph_w<T> load_treep_weight(int n) {
graph_w<T> g(n);
for (int i = 0; i < n - 1; ++i) {
int t;
T u;
std::cin >> t >> u;
g[i + 1].emplace_back(t, u);
g[t].emplace_back(i + 1, u);
}
return g;
}
#line 10 "cpplib/graph_tree/dijkstra.hpp"
/**
* @brief ダイクストラ法 O((E+V)logE)
*/
template <typename T, typename F = std::less<T>, typename Add = std::plus<T>>
struct dijkstra {
int s;
std::vector<T> diff;
std::vector<int> par;
std::vector<int> used;
dijkstra(const graph_w<T> &list, int s, T zero = T(),
T inf = std::numeric_limits<T>::max(), F f = F(), Add add = Add())
: s(s) {
int n = list.size();
diff.resize(n, inf);
par.resize(n, -1);
used.resize(n, 0);
std::priority_queue<std::pair<T, int>, std::vector<std::pair<T, int>>,
std::greater<std::pair<T, int>>>
que;
diff[s] = zero;
que.push(std::make_pair(T(), s));
while (!que.empty()) {
auto d = que.top();
que.pop();
T x;
int now;
std::tie(x, now) = d;
if (used[now])
continue;
used[now] = 1;
for (auto d2 : list[now]) {
T sa;
int to;
std::tie(to, sa) = d2;
T tmp = add(diff[now], sa);
if (f(tmp, diff[to])) {
diff[to] = tmp;
par[to] = now;
que.emplace(diff[to], to);
}
}
}
}
vector<T> get() { return diff; }
T operator[](int idx) { return diff[idx]; }
bool reachable(int t) { return par[t] != -1; }
std::vector<int> get_path(int t) {
std::vector<int> res;
while (t != s) {
res.push_back(t);
t = par[t];
}
res.push_back(s);
std::reverse(res.begin(), res.end());
return res;
}
};
#line 3 "main.cpp"
void solve() {
lint n, m, x;
cin >> n >> m >> x;
graph_w<lint> v(n);
rep(i, m) {
lint s, t, c, d;
cin >> s >> t >> c >> d;
s--;
t--;
v[s].push_back({t, d * x + c});
v[t].push_back({s, d * x + c});
}
// 1円を1/x時間で稼ぐと考えると d+c/x で比較できる
lint ans = dijkstra<lint>(v, 0)[n - 1];
if (ans >= INF / 2) {
cout << -1 << endl;
} else
cout << (ans + x - 1) / x << endl;
}
int main() {
solve();
// lint t;cin>>t;while(t--)solve();
}