[ZJ] d915: 3. 洗街車路線問題

#include<stdio.h>
#include<string.h>
#include<vector>
#define INF 999999999
using namespace std;
struct P{
    int v,c;
}in;
vector<P> s[1505];
vector<int> odd;
int tr[1505],v[1505];
int add[1505]={0},d[1505][1505];
int dp[1<<15];
int Nodd,n,m,st;
void dijkstra(int p){
    memset(v,0,sizeof(v));
    int i,j,minn,k;
    d[p][p]=0;
    for(i=1;i<=n;i++){
        minn=INF;
        for(j=1;j<=n;j++)
            if(d[p][j]<minn && v[j]==0)
                minn=d[p][j],k=j;
        v[k]=1;
        for(j=0;j<s[k].size();j++){
            in=s[k][j];
            if(d[p][k]+in.c<d[p][in.v])
                d[p][in.v]=d[p][k]+in.c;
        }
    }
}
int cnt(int N){
    if(N==0) return 0;
    if(dp[N]!=INF) return dp[N];
    int i,j,tmp;
    for(i=0;i<Nodd;i++){
        for(j=i+1;j<Nodd;j++){
            if(N&(1<<j) && N&(1<<i)){
                tmp=cnt(N-(1<<j)-(1<<i));
                if(d[odd[i]][odd[j]]+tmp<dp[N])
                    dp[N]=d[odd[i]][odd[j]]+tmp;
            }
        }
    }
    return dp[N];
}
int main(){
    int a,b,c,i,j,k,ans=0,N=0;
    scanf("%d%d%d",&n,&m,&st);
    for(i=0;i<m;i++){
        scanf("%d%d%d",&a,&b,&c);
        s[a].push_back((P){b,c});
        s[b].push_back((P){a,c});
        add[a]++,add[b]++;
        ans+=c;
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            d[i][j]=INF;
    for(i=1;i<=n;i++)
        if(add[i]%2==1){
            odd.push_back(i);
            dijkstra(i);
        }
    Nodd=odd.size();
    for(i=0;i<Nodd;i++)
        N+=(1<<i);
    for(i=0;i<=N;i++)
        dp[i]=INF;
    printf("%d\n",ans+cnt(N));
}