fork download 
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cmath>
  4. #include<vector>
  5. #include<stack>
  6. #include<queue>
  7. #include<map>
  8. #include<set>
  9. #include<algorithm>
  10. #include<functional>
  11. #include<cstring>
  12. #include<deque>
  13. #include<climits>
  14. using namespace std;
  15. struct edge{
  16.     int e,w;
  17. 	edge(){}
  18. 	edge(int _e,int _w){
  19. 		e=_e;w=_w;
  20. 	}
  21. };
  22. vector<edge>V[1001];
  23. vector<int>Odd;
  24.  
  25. int path[1001];
  26. int omap[16][16];
  27. int DP[65536];
  28. int log2(int w){
  29.     int ans=0;
  30.     while(w>(1<<ans))ans++;
  31.     return ans;
  32. }
  33. int dfs(int key)
  34. {
  35.     if(DP[key]!=1000000)return DP[key];
  36.     if(key==0)return 0;
  37.     int hi=1,tmp=1;
  38.     while(key>=tmp){
  39.         if(key&tmp)hi=tmp;
  40.         tmp<<=1;
  41.     }
  42.     int ans=INT_MAX;
  43.     for(int low=hi>>1;low;low>>=1)
  44.     {
  45.         if(key&low){
  46.             ans=min(ans,omap[log2(hi)][log2(low)]+dfs(key-hi-low));
  47.         }
  48.     }
  49.     return DP[key]=ans;
  50. }
  51.  
  52. void makeSP(int s)
  53. {
  54.     queue<int> qu;
  55.     bool inqu[1001]={false};
  56.     memset(path,0x3f,sizeof(path));
  57.     path[s]=0;
  58.     qu.push(s);
  59.     while(!qu.empty())
  60.     {
  61.         int T=qu.front();qu.pop();
  62.         inqu[T]=false;
  63.         for(vector<edge>::iterator vit=V[T].begin();vit!=V[T].end();++vit)
  64.         {
  65.             if(path[vit->e]>path[T]+vit->w)
  66.             {
  67.                 path[vit->e]=path[T]+vit->w;
  68.                 if(!inqu[vit->e])
  69.                 {
  70.                     qu.push(vit->e);
  71.                     inqu[vit->e]=true;
  72.                 }
  73.             }
  74.         }
  75.     }
  76. }
  77.  
  78. int main()
  79. {
  80.     int N,M,S,E,s,e,w;
  81.     int ans;
  82.     int deg[1001];
  83.     while(~scanf("%d%d%d%d",&N,&M,&S,&E))
  84.     {
  85. 		ans=0;
  86.         memset(deg,0,sizeof(deg));
  87.         for(int i=1;i<=N;++i)V[i].clear();
  88.         while(M--){
  89.             scanf("%d%d%d",&s,&e,&w);
  90.             deg[s]++;
  91.             deg[e]++;
  92.             V[s].push_back(edge(e,w));
  93.             V[e].push_back(edge(s,w));
  94.             ans+=w;
  95.         }
  96.         V[S].push_back(edge(E,1E7));deg[S]++;
  97.         V[E].push_back(edge(S,1E7));deg[E]++;
  98.         Odd.clear();
  99.         for(int i=1;i<=N;++i)
  100.             if(deg[i]%2==1)
  101.                 Odd.push_back(i);
  102.         memset(omap,0x3f,sizeof(omap));
  103.         for(int i=0;i<Odd.size();++i)
  104.         {
  105.             makeSP(Odd[i]);
  106.             for(int j=0;j<Odd.size();++j)
  107.                 omap[i][j]=path[Odd[j]];
  108.         }
  109.         for(int i=0;i<65536;++i)DP[i]=1000000;
  110.         printf("%d\n",ans+dfs((1<<Odd.size())-1));
  111.     }
  112.     return 0;
  113. }
  114.  
Success #stdin #stdout 0s 3708KB
comments (?)
stdin 
6 10 1 5
1 2 1
1 3 1
2 3 1
2 4 2
2 5 1
3 4 1
3 5 1
4 5 1
4 6 1
5 6 1
3 3 1 2
1 2 4
1 3 6
2 3 5
stdout 
13
19
https://ideone.com/9mfQE5
language:
C++14 (gcc 8.3)
created:
9 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!