結果

問題 No.2739 Time is money
コンテスト
ユーザー rii922
提出日時 2024-04-20 19:31:59
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,595 bytes
コンパイル時間 3,553 ms
コンパイル使用メモリ 269,560 KB
実行使用メモリ 318,288 KB
最終ジャッジ日時 2024-10-12 17:23:18
合計ジャッジ時間 7,811 ms
ジャッジサーバーID
（参考情報） 		judge / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 1 TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define reps(i, n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
#define rrep(i, n) for(int i=((int)(n)-1); i>=0; --i)
#define rreps(i, n) for(int i=((int)(n)); i>0; --i)
#define all(v) (v).begin(), (v).end()
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vvvi = vector<vector<vector<int>>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using vvvl = vector<vector<vector<ll>>>;
using vs = vector<string>;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<class T>bool chmaxeq(T &a, const T &b) { if (a<=b) { a=b; return 1; } return 0; }
template<class T>bool chmineq(T &a, const T &b) { if (b<=a) { a=b; return 1; } return 0; }
bool yes(bool a) { cout << (a?"yes":"no") << endl; return a; }
bool Yes(bool a) { cout << (a?"Yes":"No") << endl; return a; }
bool YES(bool a) { cout << (a?"YES":"NO") << endl; return a; }
void _main();
int main() { cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(16); _main(); return 0; }

struct UnionFind {
  vector<int> d;
  UnionFind(int n=0): d(n,-1) {}
  int find(int x) {
    if (d[x] < 0) return x;
    return d[x] = find(d[x]);
  }
  bool unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return false;
    if (d[x] > d[y]) swap(x,y);
    d[x] += d[y];
    d[y] = x;
    return true;
  }
  bool same(int x, int y) { return find(x) == find(y);}
  int size(int x) { return -d[find(x)];}
};

void _main() {
	ll N, M, X; cin >> N >> M >> X;
	vector<vector<pair<ll, pl>>> g(N);
	UnionFind uf(N);
	rep(i, M) {
		ll u, v, C, T; cin >> u >> v >> C >> T;
		u--; v--;
		g[u].push_back({v, {C, T}});
		g[v].push_back({u, {C, T}});
		uf.unite(u, v);
	}
	if (!uf.same(0, N-1)) {
		cout << -1 << endl;
		return;
	}
	g[0].push_back({0, {-X, 1}});
	vector<map<ll, ll>> d(N);
	priority_queue<pl, vector<pl>, greater<pl>> q;
	d[0][0] = 0;
	q.push({0, 0});
	ll ans = 1LL << 60;
	while (!q.empty() && q.top().first < ans) {
		pl p = q.top();
		q.pop();
		ll m = d[p.second][p.first];
		for (auto &x : g[p.second]) {
			if (m-x.second.first < 0) continue;
			if (chmax(d[x.first][p.first+x.second.second], m-x.second.first)) {
				q.push({p.first+x.second.second, x.first});
				if (x.first == N-1) chmin(ans, p.first+x.second.second);
			}
		}
	}
	cout << ans << endl;
}
0