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

• 問題: No.2387 Yokan Factory
• ユーザー: x.t.
• 提出日時: 2023-07-21 22:23:08
• 言語: C++14 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 384 ms / 5,000 ms
• コード長: 2,457 bytes
• コンパイル時間: 1,736 ms
• コンパイル使用メモリ: 172,972 KB
• 実行使用メモリ: 10,632 KB
• 最終ジャッジ日時: 2024-09-21 23:53:26
• 合計ジャッジ時間: 6,549 ms
• ジャッジサーバーID （参考情報）: judge4 / judge1

ファイルパターン	結果
sample	AC * 3
other	AC * 35

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
// Problem: No.2387 Yokan Factory No.2387 羊羹工厂
// Contest: yukicoder
// URL: https://yukicoder.me/problems/no/2387
// Memory Limit: 512 MB
// Time Limit: 5000 ms
// 
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;
typedef pair<ll,ll> pll;
ll ksm(ll n,ll p,int mod){
    int ans=1;
    while(p){
        if(p&1) ans=(ans*n)%mod;
        n=(n*n)%mod;p>>=1;
    }
    return ans;
}
ll inv(ll b,ll c=mod) {return ksm(b,c-2,c);}
class Num{
public:
    ll num;
    Num(ll x) {num=(x%mod+mod)%mod;}
    Num operator+(Num p) {return Num(num+p.num);}
    Num operator-(Num p) {return Num(num-p.num);}
    Num operator*(Num p) {return Num(num*p.num);}
    Num operator/(Num p) {return Num(num*inv(p.num));}
    Num operator=(Num p) {this->num=p.num;return *this;}
    friend ll get(Num p) {return p.num;}
};
int h[N],w[N][2],e[2*N],ne[2*N],idx;
ll dist[N];
bool st[N]; // 如果为true说明这个点的最短路径已经确定
int n, m;
ll X;
void add(int a,int b,int c1,int c2){ //将b插入头结点为a的链表中去
    e[idx] = b, w[idx][0] = c1,w[idx][1]=c2, ne[idx] = h[a], h[a] = idx ++ ;
}
bool dijkstra(ll x)
{
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    priority_queue<pll, vector<pll>, greater<pll>> heap; 
    heap.push({ 0, 1 });
    while(heap.size())
    {
        auto k = heap.top(); // 取不在集合S中距离最短的点
        heap.pop();
        int ver = k.second;
        ll distance = k.first;
        if(st[ver]) continue;
        st[ver] = true;
        for(int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i]; // i只是个下标，e中在存的是i这个下标对应的点。
            if(w[i][1]<x) continue;
            if(dist[j] > distance + w[i][0])
            {
                dist[j] = distance + w[i][0];
                heap.push({ dist[j], j });
            }
        }
    }
    return dist[n]<=X;
}
void solve() {
    memset(h,-1,sizeof h);
    cin>>n>>m>>X;
    while(m--) {
        int u,v,ai,bi;
        cin>>u>>v>>ai>>bi;
        add(u,v,ai,bi),add(v,u,ai,bi);
    }
    ll l=-1,r=1e9+1;
    while(l+1<r) {
        ll mid = (l + r) >> 1;
        memset(st,0,sizeof st);
        if(dijkstra(mid)) l = mid;
        else  r=mid;
    }
    cout<<l<<endl;
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T=1;
    //cin>>T;
    while(T--) {
        solve();
    }
    return 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX