感谢@似水流年 翻译

题意:

在一个强联通图上,有n个人要打车,他们都在某点上(2<=n<=15)

允许拼车,但一个车上最多4个人

打一个车的代价是路费+起步价,起步价给定输入,路费即路程的权值和

解法:

先dijkstra那么几次,以初始点和每个目的地为中心dijkstra一发

然后..dp一发..

复杂度[tex]O(4 * 2^n * n^2)[/tex]

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct edge
{
    int y;
    int weight;
    edge * next;
};
edge * li[100005];
edge * new_edge()
{
    static edge a[100005];
    static int top=0;
    return &a[top++];
}
void insert_edge(int x,int y,int z)
{
    edge * t=new_edge();
    t->y=y;
    t->weight=z;
    t->next=li[x];
    li[x]=t;
}
int a[100005];
int dist[100005];
int dis[25][25];
bool visit[100005];
void dijkstra(int num)
{
    priority_queue<pair<int,int> > q;
    memset(dist,-1,sizeof(dist));
    memset(visit,0,sizeof(visit));
    q.push(make_pair(0,num));
    dist[num]=0;
    for (;!q.empty();)
    {
        int x=q.top().second;
        q.pop();
        if (visit[x]) continue;
        visit[x]=true;
        edge * t;
        for (t=li[x];t!=0;t=t->next)
        {
            if ((dist[t->y]==-1)||(dist[t->y]>dist[x]+t->weight))
            {
                dist[t->y]=dist[x]+t->weight;
                q.push(make_pair(-dist[t->y],t->y));
            }
        }
    }
}
int dp[1<<15][5][25];
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n,m;
    scanf("%d%d",&n,&m);
    int i;
    for (i=0;i<m;i++)
    {
        int t;
        scanf("%d",&t);
        int x;
        int y;
        int z;
        scanf("%d%d%d",&x,&y,&z);
        x--;
        y--;
        insert_edge(x,y,z);
        if (t==2) insert_edge(y,x,z);
    }
    int val;
    scanf("%d",&val);
    int num;
    scanf("%d",&num);
    num--;
    int k;
    scanf("%d",&k);
    for (i=0;i<k;i++)
    {
        scanf("%d",&a[i]);
        a[i]--;
    }
    dijkstra(num);
    for (i=0;i<k;i++)
    {
        dis[k][i]=dist[a[i]];
    }
    for (i=0;i<k;i++)
    {
        dijkstra(a[i]);
        int j;
        for (j=0;j<k;j++)
        {
            dis[i][j]=dist[a[j]];
        }
    }
    for (i=0;i<(1<<k);i++)
    {
        int j;
        for (j=0;j<4;j++)
        {
            int l;
            for (l=0;l<=k;l++)
            {
                dp[i][j][l]=99999999;
            }
        }
    }
    for (i=0;i<k;i++)
    {
        dp[1<<i][0][i]=val+dis[k][i];
    }
    for (i=1;i<(1<<k);i++)
    {
        int j;
        for (j=0;j<4;j++)
        {
            int l;
            for (l=0;l<k;l++)
            {
                if (((1<<l)&i)==0) continue;
                int jj;
                for (jj=0;jj<k;jj++)
                {
                    if ((1<<jj)&i) continue;
                    dp[i^(1<<jj)][j+1][jj]=min(dp[i^(1<<jj)][j+1][jj],dp[i][j][l]+dis[l][jj]);
                    dp[i^(1<<jj)][0][jj]=min(dp[i^(1<<jj)][0][jj],dp[i][j][l]+dis[k][jj]+val);
                }
            }
        }
    }
    int min_ans=99999999;
    int t=(1<<k)-1;
    for (i=0;i<4;i++)
    {
        int l;
        for (l=0;l<k;l++)
        {
            min_ans=min(min_ans,dp[t][i][l]);
        }
    }
    printf("%d\n",min_ans);
    return 0;
}