Submission #991743

#	Time	Username	Problem	Language	Result	Execution time	Memory
991743		vjudge1	Toll (APIO13_toll)	C++17	16 / 100	0 ms	348 KiB

toll

#include<bits/stdc++.h>
#include <algorithm>  
#include <vector>
#include <unordered_map>
#define append push_back
#define int long long
#define vi vector<int>
#define pi pair<int,int>
#define vv vector<vector<int>>
#define vb vector<bool>
#define vl vector<long long>
#define ff first
#define ss second
#define ul map<int,vector<pi>>
#define us unordered_map<int,set<int>>
#define ub unordered_map<int,bool>
#define ui unordered_map<int,int>
#define ll long long 
#define fi cin.tie(NULL)
#define fu cout.tie(NULL)
using namespace std;
vi parent;
ul graph;
vi sizes;
vv edges;
int n,m,u,v,w,e,k;
vi dijkstra()
{
    vi distance(n+1,1e9);
    distance[1]=0;
    priority_queue<pi> q;
    q.push({0,1});
    while (q.size())
    {
        int now=q.top().ss;
        q.pop();
        for (auto  sp: graph[now])
        {

            if (distance[sp.ff]>distance[now]+sp.ss)
            {
                distance[sp.ff]=distance[now]+sp.ss;
                q.push({distance[sp.ff],sp.ff});
            }
        }
    }
    return distance;
    
}
vector<pi> nedges;
int get(int x){
    if( parent[x]==x) return x;
    parent[x] = get(parent[x]) ;
    return parent[x];
}
void union_(int a,int b ){
   int  a_r=get(a);
   int  b_r=get(b);
    if  (a_r==b_r) return;
    if (sizes[a_r]<sizes[b_r]) swap(a_r,b_r);
    parent[b_r]=a_r;
    sizes[a_r]+=sizes[b_r];}
bool compare(vi &a ,vi &b)
{
    if (a[2]<b[2]){return true;}
    return false;
}
 
signed main() {
    fi;fu;
    cin>>n>>m>>k;
 
for(int i=0;i<n+1;i++){parent.append(i);sizes.append(1);}
    for(int i=0;i<m;i++)
    {
        cin>>u>>v>>w;
        edges.append({u,v,w});
    }
    for(int i=0;i<k;i++)
    {
        cin>>u>>v;
        nedges.append({u,v});
    }
    u=0;v=0,w=0;
    int total=0;
    sort(edges.begin(),edges.end(),compare);
        for(int i=0 ;i<m;i++)
        {
            u=edges[i][0];
            v=edges[i][1];
            w=edges[i][2];
        // cout<<u<<" "<<v<<" "<<w<<endl;
            if (get(u)==get(v)) continue;
            else
            {
                bool ok=0;
                for(pi sp:nedges)
                {
                    if ((get(sp.ff)==get(u) and get(sp.ss)==get(v)) or (get(sp.ss)==get(u) and get(sp.ff)==get(v))) 
                    {
                        ok=1;
                        graph[sp.ff].append({sp.ss,w});
                        graph[sp.ss].append({sp.ff,w});
                        union_(sp.ff,sp.ss);
                        break;
                    }
                } 
                if (!ok)
                {
                    union_(u,v);
                        graph[u].append({v,0});
                        graph[v].append({u,0});
                }
            }
        }
        vi d=dijkstra();
        for (int i=1;i<=n;i++)
        {
            cin>>e;
            total+=e*d[i];
            // cout<<d[i]<<" ";
        }
    // for (auto i :parent){cout<<i<<" ";}
    cout<<total;
 
    
 
}

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