結果

問題 No.2387 Yokan Factory
ユーザー x.t.x.t.
提出日時 2023-07-21 22:23:08
言語 C++14
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 6 ms
6,144 KB
testcase_01 AC 7 ms
6,016 KB
testcase_02 AC 7 ms
6,144 KB
testcase_03 AC 6 ms
6,016 KB
testcase_04 AC 6 ms
5,888 KB
testcase_05 AC 6 ms
6,016 KB
testcase_06 AC 7 ms
6,016 KB
testcase_07 AC 6 ms
6,016 KB
testcase_08 AC 7 ms
6,016 KB
testcase_09 AC 6 ms
5,888 KB
testcase_10 AC 7 ms
5,888 KB
testcase_11 AC 6 ms
5,888 KB
testcase_12 AC 7 ms
6,016 KB
testcase_13 AC 6 ms
5,888 KB
testcase_14 AC 7 ms
6,144 KB
testcase_15 AC 198 ms
10,460 KB
testcase_16 AC 118 ms
10,000 KB
testcase_17 AC 353 ms
10,632 KB
testcase_18 AC 274 ms
8,756 KB
testcase_19 AC 261 ms
8,064 KB
testcase_20 AC 196 ms
7,884 KB
testcase_21 AC 384 ms
8,616 KB
testcase_22 AC 186 ms
7,728 KB
testcase_23 AC 277 ms
8,032 KB
testcase_24 AC 101 ms
7,848 KB
testcase_25 AC 158 ms
7,296 KB
testcase_26 AC 316 ms
8,304 KB
testcase_27 AC 358 ms
8,528 KB
testcase_28 AC 7 ms
6,144 KB
testcase_29 AC 9 ms
6,016 KB
testcase_30 AC 8 ms
6,016 KB
testcase_31 AC 8 ms
5,888 KB
testcase_32 AC 7 ms
6,016 KB
testcase_33 AC 8 ms
6,016 KB
testcase_34 AC 9 ms
6,144 KB
testcase_35 AC 9 ms
6,144 KB
testcase_36 AC 7 ms
6,144 KB
testcase_37 AC 7 ms
5,888 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// 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;
}
0