题解：P2483 【模板】k 短路 / [SDOI2010] 魔法猪学院

#include<bits/stdc++.h>
using namespace std;
template<typename T>
using pq=priority_queue<T,vector<T>,greater<T>>;

int n,m,ans,cnt[5005];
double tmp[5005],e;
vector<pair<int,double>>g[5005],g2[5005];
int v[5005];

void dij(int x){
    for(int i=1;i<=n;i++)tmp[i]=1e18;
    tmp[x]=0;
    pq<pair<double,int>>q;
    q.push({0,x});
    memset(v,0,sizeof(v));
    while(q.size()){
        int u=q.top().second;
        double t=q.top().first;
        q.pop();
        if(v[u])continue;
        v[u]=1;
        for(auto [v,w]:g2[u]){
            if(tmp[v]>t+w){
                tmp[v]=t+w;
                q.push({tmp[v],v});
            }
        }
    }
}

namespace dsu{
    int f[5005],sz[5005];
    void init(){
        for(int i=1;i<=n;i++)f[i]=i,sz[i]=1;
    }
    int find(int x){
        if(x==f[x])return x;
        return f[x]=find(f[x]);
    }
    void merge(int x,int y){
        x=find(x),y=find(y);
        if(x!=y){
            f[x]=y;
            sz[y]+=sz[x];
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>n>>m>>e;
    dsu::init();
    
    while(m--){
        int u,v;
        double w;
        cin>>u>>v>>w;
        g[u].emplace_back(v,w);
        g2[v].emplace_back(u,w);
    }
    
    dij(n);
    
    for(int i=2;i<n;i++){
        if(dsu::find(i)!=i)continue;
        for(int j=i+1;j<n;j++){
            if(dsu::find(j)!=j)continue;
            if(g[i].size()==1 && g2[i].size()==1 && g[i]==g[j] && g2[i]==g2[j]){
                dsu::merge(i,j);
            }
        }
    }
    
    for(int i=1;i<=n;i++){
        if(dsu::find(i)==i){
            cnt[i]=dsu::sz[i];
        }
    }
    
    using elem=pair<double,pair<int,int>>;
    multiset<elem>q;
    q.insert({tmp[1],{1,cnt[1]}});
    double sum=tmp[1]*cnt[1];
    
    while(!q.empty()){
        auto [t,p]=*q.begin();
        auto [u,times]=p;
        q.erase(q.begin());
        
        if(t>e)break;
        sum-=t*times;
        
        if(u==n){
            int add=min((int)(e/t),times);
            ans+=add;
            e-=t*add;
            continue;
        }
        
        for(auto [v,w]:g[u]){
            if(!cnt[v])continue;
            double new_t=t+w+tmp[v]-tmp[u];
            if(new_t>e)continue;
            
            int new_times=times*cnt[v];
            sum+=new_t*new_times;
            q.insert({new_t,{v,new_times}});
            
            while(sum>e){
                auto it=--q.end();
                auto [bt,bp]=*it;
                auto [bu,btimes]=bp;
                sum-=bt*btimes;
                q.erase(it);
                
                int k=(int)((e-sum)/bt);
                if(k>0){
                    sum+=bt*k;
                    q.insert({bt,{bu,k}});
                }
            }
        }
    }
    
    cout<<ans<<endl;
    
    return 0;
}