fork(5) download
copy 
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<queue>
  4. #include<string>
  5. #define FOR(i,a,b) for(int i=a;i<b;i++)
  6. #define INFI 1000000000
  7. #include <map>
  8. #include<set>
  9. using namespace std;
  10. int N,M;
  11. vector<int>v[100005];
  12. int tax[100005];
  13. bool visit[100005];
  14. int minval,last,city;
  15. int scc[100005];
  16. void DFS(int u){
  17.     visit[u]=true;
  18.     for(int i=0;i<v[u].size();i++){
  19.         int k=v[u][i];
  20.         if(!visit[k])DFS(k);
  21.     }
  22.     city++;
  23.     if(tax[u]>0 && tax[u]<minval)minval=tax[u];
  24. }
  25. bool DFS_visit(){
  26.     FOR(i,1,N+1){
  27.         if(!visit[i]){
  28.             minval=INFI;
  29.             city=0;
  30.             DFS(i);
  31.             if(minval==INFI && city<N){
  32.                 printf("-1\n"); return false;
  33.             }
  34.             scc[last++]=minval;
  35.         }
  36.     }
  37. //    if(minval==INFI){
  38. //        printf("-1\n"); return false;
  39. //    }
  40. //    scc[last++]=minval;
  41.     return true;
  42. }
  43. int main(){
  44.     scanf("%d%d",&N,&M);
  45.     int a,b;
  46.     FOR(i,0,M){
  47.         scanf("%d%d",&a,&b);
  48.         v[a].push_back(b);
  49.         v[b].push_back(a);
  50.     }
  51.     FOR(i,1,N+1){
  52.         scanf("%d",&tax[i]);
  53.     }
  54.     bool path=DFS_visit();
  55.     if(path==false)return 0;
  56.     minval=INFI;
  57.     long long sum=0;
  58.     FOR(i,0,last){
  59.         if(minval>scc[i])minval=scc[i];
  60. //        cout<<scc[i]<<"  ";
  61.         sum+=(long long)scc[i];
  62.     }
  63. //    cout<<endl<<last<<endl;
  64.     sum+=(last-2)*minval;
  65.     printf("%lld\n",sum);
  66.     return 0;
  67. }
  68.  
Success #stdin #stdout 0s 5036KB
comments (?)
stdin
copy 
3 2       
2 3
1 2
-1 
-1
-1
stdout
copy 
0
https://ideone.com/iBh5ly
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!