結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

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