题目链接:http://codeforces.com/gym/100753/attachments/download/3533/2015-german-collegiate-programming-contest-gcpc-15-en.pdf

题目翻译:

给你一个无向图

你想去某些点玩,需要在这些点待一会儿

你可以任意走这些边,走每个边有个代价

你需要从0号点出发,访问所有你要玩的点并在那里停留,最后回到0号点

在你走的过程中,你可以打一个taxi(只能一个),然后移动到任何一个点

问:

1,能不能不用taxi来完成旅行?

2,如果不能,能不能用来完成旅行?

样例:

如那个图..

解法:

总时间去掉所有停留的时间

然后求最短路,找出p个点之间两两的距离(还有0和这p个点的距离)

写个状压dp,计算出最短距离(不用taxi)和用的(把两条路之间距离修改为T即可)

代码如下:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct edge
{
    int y;
    int weight;
    edge * next;
};
edge * li[20005];
edge * new_edge()
{
    static edge a[200005];
    static int top=0;
    return &a[top++];
}
void inserts(int x,int y,int z)
{
    edge * t=new_edge();
    t->y=y;
    t->weight=z;
    t->next=li[x];
    li[x]=t;
}
void insert_edge(int x,int y,int z)
{
    inserts(x,y,z);
    inserts(y,x,z);
}
int dist[20005];
bool visit[20005];
void dijkstra(int s)
{
    memset(dist,-1,sizeof(dist));
    memset(visit,false,sizeof(visit));
    priority_queue<pair<int,int> > que;
    dist[s]=0;
    que.push(make_pair(0,s));
    for (;!que.empty();)
    {
        int now=que.top().second;
        que.pop();
        if (visit[now])
        {
            continue;
        }
        visit[now]=true;
        edge * t;
        for (t=li[now];t!=0;t=t->next)
        {
            if ((dist[t->y]==-1)||(dist[now]+t->weight<dist[t->y]))
            {
                dist[t->y]=dist[now]+t->weight;
                que.push(make_pair(-dist[t->y],t->y));
            }
        }
    }
}
int a[25];
int dis[25][25];
int dp[1<<15][25][2];
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n,p,m,s,tt;
    scanf("%d%d",&n,&p);
    scanf("%d%d%d",&m,&s,&tt);
    int i;
    for (i=0;i<p;i++)
    {
        scanf("%d",&a[i]);
        int x;
        scanf("%d",&x);
        s-=x;
    }
    for (i=0;i<m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        insert_edge(x,y,z);
    }
    a[p]=0;
    for (i=0;i<=p;i++)
    {
        dijkstra(a[i]);
        int j;
        for (j=0;j<=p;j++)
        {
            dis[i][j]=dist[a[j]];
            if (dis[i][j]==-1)
            {
                puts("impossible");
                return 0;
            }
        }
    }
    for (i=0;i<(1<<p);i++)
    {
        int j;
        for (j=0;j<=p;j++)
        {
            dp[i][j][0]=999999999;
            dp[i][j][1]=999999999;
        }
    }
    dp[0][p][0]=0;
    for (i=0;i<(1<<p);i++)
    {
        int j;
        for (j=0;j<p;j++)
        {
            if (((1<<j)&i)==0) continue;
            int k;
            for (k=0;k<p;k++)
            {
                //from j to k
                if ((1<<k)&i) continue;
                dp[i^(1<<k)][k][0]=min(dp[i^(1<<k)][k][0],dp[i][j][0]+dis[j][k]);
                dp[i^(1<<k)][k][1]=min(dp[i^(1<<k)][k][1],dp[i][j][1]+dis[j][k]);
                dp[i^(1<<k)][k][1]=min(dp[i^(1<<k)][k][1],dp[i][j][0]+tt);
            }
            if (i==(1<<p)-1)
            {
                dp[i][p][0]=min(dp[i][p][0],dp[i][j][0]+dis[j][p]);
                dp[i][p][1]=min(dp[i][p][1],dp[i][j][1]+dis[j][p]);
                dp[i][p][1]=min(dp[i][p][1],dp[i][j][0]+tt);
            }
        }
        if (i==0)
        {
            int k;
            for (k=0;k<p;k++)
            {
                //from p to k
                dp[i^(1<<k)][k][0]=min(dp[i^(1<<k)][k][0],dp[i][j][0]+dis[p][k]);
                dp[i^(1<<k)][k][1]=min(dp[i^(1<<k)][k][1],dp[i][j][1]+dis[p][k]);
                dp[i^(1<<k)][k][1]=min(dp[i^(1<<k)][k][1],dp[i][j][0]+tt);
            }
        }
    }
    if (dp[(1<<p)-1][p][0]<=s)
    {
        printf("possible without taxi\n");
    }
    else if (dp[(1<<p)-1][p][1]<=s)
    {
        printf("possible with taxi\n");
    }
    else
    {
        printf("impossible\n");
    }
    return 0;
}