C++ split

#include<bits/stdc++.h>
using namespace std;

vector<string> split(string& s,char c){
    vector<string>ans;
    string tmp = "";
    for(int i=0;i<s.size();++i){
        if(s[i]!=c) tmp+=s[i];
        else{
            ans.push_back(tmp);
            tmp="";
        }
    }
    if(!tmp.empty()) ans.push_back(tmp);
    return ans;
}

int main()
{
        //拓扑排序的加强版 附加了每个节点的代价
    freopen("input.txt","r",stdin);
    string s1;
    getline(cin,s1);
    vector<string>cost = split(s1,',');
    int n = cost.size();

    vector<int>t(n+1,0);
    //每项节点需要的代价
    for(int i=0;i<cost.size();++i){
        t[i+1]=stoi(cost[i]);
    }
    //记录每个节点的入度
    vector<int>indegree(n+1,0);
    string s2;
    getline(cin,s2);
    //图结构 记录依赖关系
    vector<vector<int>>graph(n+1);
    vector<string>depend = split(s2,';');
    //记录到每个节点的耗费代价 动态更新
    vector<int>fee(n+1,0);
    for(int i=1;i<=n;++i) fee[i]=t[i];

    for(int i=0;i<depend.size();++i){
        vector<string>tmp = split(depend[i],',');
        for(int j=0;j<tmp.size();++j){
            int node = stoi(tmp[j]);
            graph[i+1].push_back(node);
            indegree[node]++;
        }
    }
    queue<int>q;
    for(int k=1;k<=n;++k)
        if(indegree[k]==0)
            q.push(k);
    int ans = 0;
    while(!q.empty()){
        auto p = q.front();q.pop();
        ans = max(ans,fee[p]);
        for(auto& a:graph[p]){
            //出队时 更新当前元素可达的节点的代价
            fee[a]=max(fee[a],fee[p]+t[a]);
            if(--indegree[a]==0)
                q.push(a);
        }
    }
    cout<<ans<<endl;
    return 0;

}