zoj 3620制限時間におけるa点からb点までの収益最大値(状圧+探索)

edポイントに気づいても残りの時間を他のポイントへのアクセスを継続することができます.そのため、あるポイントがアクセスしたかどうか(折り返す可能性があるため)をマークするのではなく、「ある状態+出点」でマークします.

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include<queue>
using namespace std;
struct node{
	int a,b,c;
	node(int aa=0,int bb=0,int cc=0){
		a=aa;b=bb;c=cc;
	}
	bool operator < (const node &x) const{
		if(a!=x.a)
			return a<x.a;
		else if(b!=x.b)
			return b<x.b;
		else if(c!=x.c)
			return c<x.c;
	}
};
int y[15];
int x[15][15];
int vis[2048][15];
int main(){
	int n,m,t;
	while(cin>>n>>m>>t){
		memset(x,0,sizeof(x));
		memset(vis,-1,sizeof(vis));
		int st,ed;
		cin>>st>>ed;
		for(int i=0;i<n;++i)
			cin>>y[i];
		int a,b,c;
		while(m--){
			cin>>a>>b>>c;
			x[a][b]=c;
			x[b][a]=c;
		}
		queue<node> q;
		q.push(node((1<<st),st,0)); //    ，   ，  （                   ） 
		vis[1<<st][st]=0;
		int maxx=0;
		while(!q.empty()){
			node fr=q.front();
			a=fr.a,b=fr.b,c=fr.c; 
			q.pop();
			int s=0;
			if(b==ed){
				for(int i=0;i<n;++i){
					if(a&(1<<i))
						s+=y[i];
				}
				maxx=max(maxx,s);
			}
			for(int i=0;i<n;++i){
				if(x[b][i]==0) continue;
				if(c+x[b][i]<=t&&vis[a|(1<<i)][i]==-1){ //  vis  ，  MLE 
					vis[a|(1<<i)][i]=c+x[b][i];
					q.push(node((a|(1<<i)),i,c+x[b][i]));
				}
				else if(c+x[b][i]<=t&&vis[a|(1<<i)][i]>c+x[b][i]){
					vis[a|(1<<i)][i]=c+x[b][i];
					q.push(node((a|(1<<i)),i,c+x[b][i]));
				}
			}
		}
		cout<<maxx<<endl;
	}
	return 0;
}

別のdfsアプローチ:

#include <stdio.h>
#include <string.h>
int dis[10][10], room[10];
int max, s, e, n, m, t;
char psd[10];

void DFS(int x, int time, int sum)
{
    int i;
    
    if(psd[x] == 0) sum += room[x];
    psd[x] ++;

    if(x == e)
        max = sum > max? sum : max;

    for(i = 0; i < n; i++)
        if(psd[x] < n && dis[x][i] && time >= dis[x][i]) DFS(i, time-dis[x][i], sum);

    psd[x] --;
}

int main(void)
{
    int i, a, b, c;
    
    while(scanf("%d%d%d", &n, &m, &t) != EOF)
    {
        memset(dis, 0, sizeof(dis));
        memset(psd, 0, sizeof(psd));
        
        scanf("%d%d", &s, &e);
        
        for(i = 0; i < n; i++)
            scanf("%d", &room[i]);

        for(i = 0; i < m; i++)
        {
            scanf("%d%d%d", &a, &b, &c);
            dis[a][b] = c;
            dis[b][a] = c;
        }
        
        max = 0;
        DFS(s, t, 0);
        printf("%d
", max);
    }
    return 0;
}