2023icpc南京站补题

vector<PII>e[N];
int n,m,c,minn,dist[N];
bool st[N];
void Dijkstra(int u){
    minn=1e18;
    for(int i=1;i<=n;i++)dist[i]=1e18,st[i]=0;
    priority_queue<PII,vector<PII>,greater<PII> >q;
    dist[u]=0;
    q.push({dist[u],u});
    while(q.size()){
        auto [dis,ver]=q.top();
        q.pop();
        if(st[ver])continue;
        st[ver]=1;
        for(auto [v,w]:e[ver]){
            if(v==u)minn=min(minn,dis+w);
            if(st[v])continue;
            if(dist[v]>dis+w){
                dist[v]=dis+w;
                q.push({dist[v],v});
            }
        }
    }
}
void solve(){
    cin>>n>>m>>c;
    int ans=0;
    for(int i=1;i<=m;i++){
        int u,v,z;cin>>u>>v>>z;
        e[u].pb({v,z});
        if(z<=c)ans=1;
    }
    for(int i=1;i<=n;i++){
        Dijkstra(i);
        if(minn<=c){ans=2;break;}
    }
    cout<<ans<<"\n";
}