#894070 (C++14) No.2387 Yokan Factory

• 問題: No.2387 Yokan Factory
• ユーザー: bluebery1001
• 提出日時: 2023-07-21 22:19:21
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 795 ms / 5,000 ms
• コード長: 4,908 bytes
• コンパイル時間: 5,962 ms
• コンパイル使用メモリ: 266,944 KB
• 実行使用メモリ: 19,308 KB
• 最終ジャッジ日時: 2023-10-21 22:19:33
• 合計ジャッジ時間: 13,895 ms
• ジャッジサーバーID （参考情報）: judge13 / judge9

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 4,348 KB
testcase_01	AC	2 ms; 4,348 KB
testcase_02	AC	2 ms; 4,348 KB
testcase_03	AC	2 ms; 4,348 KB
testcase_04	AC	2 ms; 4,348 KB
testcase_05	AC	2 ms; 4,348 KB
testcase_06	AC	2 ms; 4,348 KB
testcase_07	AC	2 ms; 4,348 KB
testcase_08	AC	2 ms; 4,348 KB
testcase_09	AC	2 ms; 4,348 KB
testcase_10	AC	2 ms; 4,348 KB
testcase_11	AC	2 ms; 4,348 KB
testcase_12	AC	2 ms; 4,348 KB
testcase_13	AC	2 ms; 4,348 KB
testcase_14	AC	2 ms; 4,348 KB
testcase_15	AC	232 ms; 19,308 KB
testcase_16	AC	139 ms; 18,280 KB
testcase_17	AC	338 ms; 18,348 KB
testcase_18	AC	554 ms; 16,036 KB
testcase_19	AC	484 ms; 12,288 KB
testcase_20	AC	353 ms; 11,460 KB
testcase_21	AC	795 ms; 15,292 KB
testcase_22	AC	293 ms; 10,728 KB
testcase_23	AC	500 ms; 12,272 KB
testcase_24	AC	172 ms; 11,240 KB
testcase_25	AC	236 ms; 8,668 KB
testcase_26	AC	602 ms; 13,576 KB
testcase_27	AC	744 ms; 14,860 KB
testcase_28	AC	4 ms; 4,348 KB
testcase_29	AC	4 ms; 4,348 KB
testcase_30	AC	4 ms; 4,348 KB
testcase_31	AC	3 ms; 4,348 KB
testcase_32	AC	3 ms; 4,348 KB
testcase_33	AC	3 ms; 4,348 KB
testcase_34	AC	5 ms; 4,348 KB
testcase_35	AC	3 ms; 4,348 KB
testcase_36	AC	3 ms; 4,348 KB
testcase_37	AC	2 ms; 4,348 KB

コンパイルメッセージ

main.cpp: In function 'll zaatu(std::vector<long long int>&)':
main.cpp:60:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   60 |     for(auto&&[key,val]:m)val=ret++;
      |               ^

ソースコード

using namespace std;
#include<bits/stdc++.h>
void _main();int main(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);_main();return 0;}
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
typedef long long ll;typedef long double ld;template<class ll>inline bool chmax(ll&a,ll b){if(a<b){a=b;return 1;}return 0;}template<class ll>inline bool chmin(ll& a,ll b){if(a>b){a=b;return 1;}return 0;}
#define rep(i, star,fini) for(int i=star;i<fini;i++)
#define ALL(x) std::begin(x),std::end(x)
#define INF ((1LL<<62)-(1LL<<31))
#define bit(x,i) (((x)>>(i))&1)
inline void scan(){}
template<class Head,class... Tail>
inline void scan(Head&head,Tail&... tail){std::cin>>head;scan(tail...);}
#define LL(...) ll __VA_ARGS__;scan(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;scan(__VA_ARGS__)
inline void print(){}
template<class Head,class... Tail>
inline void print(Head&head,Tail&... tail){std::cout<<head<<" ";print(tail...);cout<<endl;}
template<typename T>
std::istream &operator>>(std::istream&is,std::vector<T>&v){for(T &in:v){is>>in;}return is;}
template<typename T>
std::ostream &operator<<(std::ostream&os,const std::vector<T>&v){for(auto it=std::begin(v);it!=std::end(v);){os<<*it<<((++it)!=std::end(v)?" ":"");}return os;}
long double my_distance(long double xi,long double yi,long double xj,long double yj){return sqrt(abs((xi-xj)*(xi-xj))+abs((yi-yj)*(yi-yj)));}
//Union-Find from https://zenn.dev/reputeless/books/standard-cpp-for-competitive-programming/viewer/union-find
class UnionFind{public:UnionFind()=default;explicit UnionFind(size_t n):m_parentsOrSize(n, -1){}int find(int i){if(m_parentsOrSize[i]<0){return i;}return(m_parentsOrSize[i]=find(m_parentsOrSize[i]));}void merge(int a,int b){a=find(a);b=find(b);if(a!=b){if(-m_parentsOrSize[a]<-m_parentsOrSize[b]){std::swap(a,b);}m_parentsOrSize[a]+=m_parentsOrSize[b];m_parentsOrSize[b]=a;}}bool connected(int a,int b){return (find(a)==find(b));}int size(int i){return -m_parentsOrSize[find(i)];}private:std::vector<int>m_parentsOrSize;};
//ll MOD = INF;
//ll MOD = 1000000007;
ll MOD = 998244353;
ll modpow(ll a,ll n){ll res=1;while(n>0){if(n&1)res=res*a%MOD;a=a*a%MOD;n>>=1;}return res;}
ll modinv(ll a){return modpow(a,MOD-2);}
bool iskaibun(string s){ll k = s.size();rep(i,0,k/2){if(s[i]!=s[k-1-i]){return false;}}return true;}
struct BIT_t{private:vector<ll> bit_t;int N;public:BIT_t(int size){N = size;bit_t.resize(N+1);}void add(int a, int w){for(int x=a;x<=N;x+=x&-x)bit_t[x]+=w;}int sum(int a){ll ret=0;for(int x=a;x>0;x-=x&-x) ret += bit_t[x];return ret;}};
ll tentou(vector<ll>* v_t){BIT_t v_t_BIT(*max_element(ALL(*v_t))+2);ll res=0,num=0;for(auto&&i:*v_t){res += num-v_t_BIT.sum(i+1);v_t_BIT.add(i+1,1);}return res;}
//string replace(string &replacedStr,string from,string to) {ll pos=0;int toLen = to.length();while((pos=replacedStr.find(from,pos))!=string::npos){replacedStr.replace(pos, from.length(), to);pos += toLen;}return replacedStr;}
#include <atcoder/all>
using namespace atcoder;
string replace(const string&moto,const string &from, const string&too) {
  int from_len = from.size();
  string tmp = from + moto;
  int tmp_len = tmp.size();
  vector<int> za = z_algorithm(tmp);
  string ret = "";
  for (int i = from_len; i < tmp_len;) {
    if (za[i] >= from_len) {
      ret += too;
      i += from_len;
    } else {
      ret += tmp[i];
      i++;
    }
  }
  return ret;
}

ll zaatu(vector<ll>&A){
    map<ll,ll>m;
    for(auto&&x:A)m[x]=0;
    ll ret = 0;
    for(auto&&[key,val]:m)val=ret++;
    for(auto&&x:A)x=m[x];
    return ret;
}
pair<ll,ll>pairmax(pair<ll,ll>a,pair<ll,ll>b){
    if(a.first+a.second==b.first+b.second){
        if(a.first>b.first)return a;
        else return b;
    }
    if(a.first+a.second>b.first+b.second)return a;
    else return b;
}

vector<ll>enumdiv(ll n){
    vector<ll>s;
    for(ll i = 1;i*i<=n;i++){
        if(n%i==0){s.push_back(i);if(i*i!=n)s.push_back(n/i);}
        
    }
    return s;
}
using mint = modint998244353;
void _main(){
    LL(n,m,x);
    //行先、所要時間、幅
    vector<vector<vector<ll>>>g(n);
    rep(i,0,m){
        LL(u,v,a,b);
        g[--u].push_back({--v,a,b});
        g[v].push_back({u,a,b});
    }
    ll ok = 0,ng= 1000000009;
    while(abs(ok-ng)>1){
        ll mid = (ok+ng)/2;
        vector<ll>dist(n,INF);
        dist[0]=0;
        priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>>pq;
        pq.push({0,0});
        while(!pq.empty()){
            ll pos = pq.top().second,d = pq.top().first;
            pq.pop();
            if(dist[pos]<d)continue;
            for(auto&&i:g[pos]){
                if(mid>i[2])continue;
                if(chmin(dist[i[0]],d+i[1])){
                    pq.push({dist[i[0]],i[0]});
                }
            }
        }
        if(dist[n-1]<=x)ok=mid;
        else ng = mid;
    }
    cout<<(ok!=0?ok:-1)<<endl;
}