fork download
copy 
  1. #include<iostream>
  2. #include <list>
  3. #include<cstdio>
  4. #include<cstdlib>
  5. #define minimum(a,b) a<b?a:b
  6. #define MAX 123456789
  7.  
  8. using namespace std;
  9.  
  10. int *val,disjoint=0;
  11. long long int mi,ans=0,min_all;
  12.  
  13.  
  14. int read()
  15. {
  16.     int t=0;char c;
  17.     c=getchar();
  18.     while((c<'0'||c>'9'))c=getchar();
  19.     while(c>='0'&&c<='9')
  20.     {
  21.         t=(t<<3)+(t<<1)+c-'0';
  22.         c=getchar();
  23.     }
  24.     return t;
  25. }
  26.  
  27. class Graph
  28. {
  29.     int V;
  30.     list<int> *adj;
  31.     void DFSUtil(int v, bool visited[]);
  32. public:
  33.     Graph(int V);
  34.     void addEdge(int v, int w);
  35.     void DFS();
  36. };
  37.  
  38. Graph::Graph(int V)
  39. {
  40.     this->V = V;
  41.     adj = new list<int>[V];
  42.     val=(int *)malloc(sizeof(int)*(V));
  43. }
  44.  
  45. void Graph::addEdge(int v, int w)
  46. {
  47.     adj[v].push_back(w);
  48. }
  49.  
  50. void Graph::DFSUtil(int v, bool visited[])
  51. {
  52.     visited[v] = true;
  53.  
  54.     if(val[v]>=0)
  55.     {
  56.         //printf("{ %lld %d",mi,min_all);
  57.         mi=minimum(val[v],mi);
  58.         min_all=minimum(val[v],min_all);
  59.         //printf("%lld %d }\n",mi,min_all);
  60.     }
  61.  
  62.  
  63.     list<int>::iterator i;
  64.     for(i = adj[v].begin(); i != adj[v].end(); ++i)
  65.         if(!visited[*i])
  66.             DFSUtil(*i, visited);
  67. }
  68.  
  69. void Graph::DFS()
  70. {
  71.     bool *visited = new bool[V];
  72.     for(int i = 0; i < V; i++)
  73.         visited[i] = false;
  74.  
  75.     for(int i=1;i<V;i++)
  76.     {
  77.         if(visited[i]==false)
  78.         {
  79.             mi=MAX;
  80.             //printf("$%lld\n",mi);
  81.  
  82.             disjoint++;
  83.  
  84.             DFSUtil(i, visited);
  85.  
  86.             if(mi==MAX)
  87.             {
  88.  
  89.                 ans=-1;
  90.                 //printf("**\n");
  91.                 break;
  92.             }
  93.             else
  94.             ans+=mi;
  95.             //printf("%lld**\n",ans);
  96.         }
  97.         if(ans==-1)break;
  98.  
  99.     }
  100. }
  101.  
  102. int main()
  103. {
  104.     int n,m;
  105.     n=read();
  106.     m=read();
  107.  
  108.  
  109.  
  110.         Graph g(n+1);
  111.         min_all=MAX;	
  112.         for(int i=0;i<m;i++)
  113.         {
  114.             int a,b;
  115.             a=read();
  116.             b=read();
  117.             g.addEdge(a,b);
  118.         }
  119.         for(int i=1;i<=n;i++)
  120.             scanf("%d",&val[i]);
  121.  
  122.     if(n==1)
  123.     {
  124.         printf("0\n");
  125.     }
  126.     else
  127.     {
  128.         g.DFS();
  129.         if(disjoint==1)
  130.         {
  131.             printf("0\n");
  132.         }
  133.         else
  134.         {
  135.             if(ans==-1)
  136.                 printf("-1\n");
  137.             else
  138.             {
  139.                 disjoint-=2;
  140.                 ans+=disjoint*min_all;
  141.                 printf("%lld\n",ans);
  142.             }
  143.         }
  144.     }
  145.     return 0;
  146. }
  147.  
Success #stdin #stdout 0s 2820KB
comments (?)
stdin
copy 
8 5
2 3
4 5
6 7
7 8
8 2
1
-1 
2
3
-1
4
1
3
stdout
copy 
9
https://ideone.com/xYz5kE
language:
C++ 4.3.2 (gcc-4.3.2)
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!