求助一下E题,跑dij 然后三分得到一个答案区间,为啥超时了啊,显示只过了
75%数据,考虑到了longlong的问题,都换成longlong了还是超时。。。 #include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
#define fi first
#define sc second
#define pb push_back
using namespace std;
const int N=1e6+7;
const ll INF=1e18;
ll dis[N];ll n,m,h;
struct node{ll k,b,to;};
vector<node> G[N];
ll check(ll x) {
for(ll i=1;i<=n;i++) dis[i]=INF;
dis[1]=0;
priority_queue<pii,vector<pii>,greater<pii> > q;
q.push(pii(1,0));
while(!q.empty()) {
ll u=q.top().fi;ll d=q.top().sc;
q.pop();
if(dis[u]<d) continue;
for(auto t:G[u]) {
ll v=t.to,k=t.k,b=t.b;
if(dis[v]>dis[u]+1ll*k*x+b) {
dis[v]=dis[u]+1ll*k*x+b;
q.push(pii(v,dis[v]));
}
}
}return dis[n];
}
int main() {
cin>>n>>m>>h;
for(ll i=1;i<=m;i++) {
ll u,v,k,b;scanf("%lld %lld %lld %lld",&u,&v,&k,&b);
G[u].pb(node{k,b,v});
}
ll l=0,r=h;
while(l+10<r) {
ll mid=l+r>>1;
ll smid=r+mid>>1;
if(check(mid)>check(smid)) r=smid;
else l=mid;
}
ll ans=-INF;
for(ll i=l;i<=r;i++) {
ans=max(ans,check(i));
}printf("%lld\n",ans);
return 0;
}
全部评论
(1) 回帖