厦门大学“网宿杯“17届程序设计竞赛决赛（同步赛）E.芜湖起飞

1.三分+最短路
参考 苟且的狮子 博客

https://blog.nowcoder.net/n/1fb0276367aa44df861b17f185653058

#include<bits/stdc++.h>
#define ll long long

#define pr pair<ll,ll>

using namespace std;


const int N=2e5+10;
const ll inf=1e18;
struct node{
    int v,len,next;
}a[N*2];
int pre[N],cnt=0;
ll dis[N],vis[N];
ll k[N],b[N];
int n,m,h;

void add( int u,int v,int len )
{
//    a[cnt].v=v , a[cnt].len=len , a[cnt].next=pre[u];
    a[cnt]={ v,len,pre[u] };
    pre[u]=cnt++;
}

void init()
{
    memset(pre,-1,sizeof(pre)),cnt=0;
}

ll check( ll x,int s=1 ) // 起点 
{ 
    memset( dis,0x3f,sizeof(dis) );
    memset( vis,0,sizeof(vis) );
    priority_queue<pr,vector<pr>,greater<pr> > q;
    q.push( make_pair(0,s) );
    dis[s]=0;
    while( q.size() ) 
    {
        int u=q.top().second;
        q.pop();
        vis[u]=1;
        for( int i=pre[u];~i;i=a[i].next )
        {
            int v=a[i].v,id=a[i].len;
            ll len=k[id]*x+b[id];

            if( !vis[v] && dis[v]>dis[u]+len )
            {
                dis[v]=dis[u]+len;
                q.push( make_pair(dis[v],v) );
            }
        }
    }
    return dis[n]; 
}



void solve()
{
    int l=0,r=h;
    ll ans=-1e18; 
    while( r-l>5 )
    {
        int mid1=l+(r-l)/3,mid2=r-(r-l)/3;
        ll ans1=check(mid1),ans2=check(mid2);
        if( ans1<ans2 ) l=mid1;
        else r=mid2;
    }
    for( int i=l;i<=r;i++ ) 
    {
        ans=max(ans,check(i));
    }

    printf("%lld\n",ans);
}


int main()
{
    scanf("%d%d%d",&n,&m,&h);

    init();
    int x,y,z;
    for( int i=1;i<=m;i++ )
    {
        scanf("%d%d%lld%lld",&x,&y,&k[i],&b[i]); 
        add(x,y,i);
//        add(y,x,i);
    }
    solve();

}