結果
問題 | No.2387 Yokan Factory |
ユーザー |
![]() |
提出日時 | 2023-07-21 21:55:37 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 586 ms / 5,000 ms |
コード長 | 4,466 bytes |
コンパイル時間 | 1,503 ms |
コンパイル使用メモリ | 130,672 KB |
最終ジャッジ日時 | 2025-02-15 16:49:22 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
// #pragma GCC target("avx2")// #pragma GCC optimize("O3")// #pragma GCC optimize("unroll-loops")#include <algorithm>#include <bitset>#include <cassert>#include <cmath>#include <complex>#include <climits>#include <iomanip>#include <iostream>#include <map>#include <queue>#include <set>#include <string>#include <tuple>#include <vector>using namespace std;using lg = long long;using pii = pair<int, int>;using pll = pair<lg, lg>;#define TEST cerr << "TEST" << endl#define AMARI 998244353// #define AMARI 1000000007#define TEMOTO ((sizeof(long double) == 16) ? false : true)#define TIME_LIMIT 1980 * (TEMOTO ? 1 : 1000)#define el '\n'#define El '\n'#define mpr make_pair#define LLINF LLONG_MAX//ダイクストラ//引数はグラフのvectorと始点となるノード// ただしグラフのvectorの中身はg[i][j] = {c,t}の時、点iから出ているj番目の矢印は、コストcでtへ向かうという意味// pairのfirstがコストなので注意!!!!// {他のノードへの距離を入れたvector,経路復元において1個前はどこに戻るか}を返す関数//s→始点となるノードpair<vector<long long>, vector<int>> ococo_dijkstra(vector<vector<pair<long long, int>>> const& g, int s) {vector<long long> distance(g.size(), LLINF);priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> que;que.emplace(0, s);vector<bool> visited(g.size(), false);distance[s] = 0;vector<int> prev(g.size(), -1);prev[s] = s;while (!que.empty()) {int karis = que.top().second;que.pop();if (!visited[karis]) {for (int i = 0; i < g[karis].size(); i++) {if (distance[g[karis][i].second] > distance[karis] + g[karis][i].first) {distance[g[karis][i].second] = distance[karis] + g[karis][i].first;que.emplace(distance[g[karis][i].second], g[karis][i].second);prev[g[karis][i].second] = karis;}}}visited[karis] = true;}pair<vector<long long>, vector<int>> ans;ans.first = distance;ans.second = prev;return ans;}bool func(vector<vector<pair<long long,int>>> const& g,lg x, lg c){pair<vector<long long>, vector<int>> temp = ococo_dijkstra(g,0);//cerr << temp.first[g.size() - 1] << El;if(temp.first[g.size() - 1] <= x){//cerr << c << " true" << El;return true;}else{//cerr << c << " false" << el;return false;}}#define MULTI_TEST_CASE falsevoid solve(void) {int n,m;lg x;cin >> n >> m >> x;//長さがxを超えないもので一番太いやつ//{haba,nagasa,u,v}vector<pair<lg,pair<lg,pii>>> edge(m);for(int i = 0; i < m; i++){cin >> edge[i].second.second.first >> edge[i].second.second.second >> edge[i].second.first >> edge[i].first;edge[i].second.second.first--;edge[i].second.second.second--;}sort(edge.rbegin(),edge.rend());//答えの幅は[l,r]の中にあるlg l = 0,r = 1000000001;while(r - l >= 2){lg c = (l + r) / 2;vector<vector<pair<long long,int>>> g(n);for(int i = 0; i < m; i++){//cerr << edge[i].first << ' ' << c << El;if(edge[i].first < c)break;g[edge[i].second.second.first].push_back(mpr(edge[i].second.first,edge[i].second.second.second));g[edge[i].second.second.second].push_back(mpr(edge[i].second.first,edge[i].second.second.first));}if(func(g,x,c))l = c;else r = c - 1;}lg ans = -1;for(lg c = l; c <= r; c++){//cerr << c << el;vector<vector<pair<lg,int>>> g(n);for(int i = 0; i < m; i++){if(edge[i].first < c)break;g[edge[i].second.second.first].push_back(mpr(edge[i].second.first,edge[i].second.second.second));g[edge[i].second.second.second].push_back(mpr(edge[i].second.first,edge[i].second.second.first));}//cerr << c << el;if(func(g,x,c))ans = c;else break;}cout << ans << el;return;}void calc(void) {return;}int main(void) {cin.tie(nullptr);ios::sync_with_stdio(false);calc();int t = 1;if (MULTI_TEST_CASE) cin >> t;while (t--) {solve();}return 0;}