Submission #421878

#	Time	Username	Problem	Language	Result	Execution time	Memory
421878		Apiram	Toll (APIO13_toll)	C++14	0 / 100	0 ms	204 KiB

toll

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m,k;
    cin>>n>>m>>k;
    vector<int>indegree(n,0);
    vector<vector<pair<int,int>>>in(n),out(n);
    for (int i =0;i<m;++i){
        int a,b,c;
        cin>>a>>b>>c;
        --a,--b;
        out[a].push_back({b,c});
        in[b].push_back({a,c});
        indegree[a]=max(indegree[a],c);
        indegree[b]=max(indegree[b],c);
    }
    vector<pair<int,int>>need;
    for (int i=0;i<k;++i){
        int a,b;
        cin>>a>>b;
        a--,b--;
        need.push_back({a,b});
    }
    vector<int>people(n);
    for (int i =0;i<n;++i){
        cin>>people[i];
    }
    int64_t score=0;
    for (int i =0;i<k;++i){
        int x=need[i].first;
        int y=need[i].second;
        int cost = max(indegree[x],indegree[y]);
        vector<bool>visited(n,false);
        queue<int>q;
        q.push(max(x,y));
        visited[max(x,y)]=true;
        while(!q.empty()){
            int u = q.front();
            q.pop();
            for (auto x:out[u]){
                if (!visited[x.first]){
                    visited[x.first]=true;
                    q.push(x.first);
                }
            }
        }
        int ppl = 0;
        for (int i =0;i<n;++i){
            if (visited[i])ppl+=people[i];
        }
        //cout<<cost<<endl;
        score+=ppl*(cost-1);
        
    }
    cout<<score<<endl;
    return 0;
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 18
• Subtask 3: 0 / 22
• Subtask 4: 0 / 22
• Subtask 5: 0 / 22