其实是个很水的状压DP，我还WA了三发。。
用 f [ i ] [ j ] f[i][j] f[i][j]表示访问过的商店状态为 i i i，当前刚从 j j j出来，所需的最小时间。
然而有一些细节。。

#include <bits/stdc++.h> using namespace std; const int M=16; const int N=51; int f[1<<M][M],m; int L[M],r[M],t[M]; int a[N][N]; template<class T> void checkmin(T &a,const T &b) { if (b<a) a=b; } template<class T> void checkmax(T &a,const T &b) { if (b>a) a=b; } class TravellingPurchasingMan { public: int maxStores( int N, vector <string> interestingStores, vector <string> roads ) ; }; int TravellingPurchasingMan::maxStores(int n, vector <string> iss, vector <string> roads) { m=iss.size(); memset(a,0x3f,sizeof a); int x,y,z; for(int i=0;i<roads.size();i++){ stringstream ss; ss<<roads[i]; ss>>x>>y>>z; a[x][y]=a[y][x]=z; } for(int i=0;i<n;i++) a[i][i]=0; for(int i=0;i<n;i++) for(int j=0;j<n;j++) for(int k=0;k<n;k++) a[j][k]=min(a[j][k],a[j][i]+a[i][k]); memset(f,0x3f,sizeof f); for(int i=0;i<m;i++){ stringstream ss; ss<<iss[i]; ss>>L[i]>>r[i]>>t[i]; if (a[n-1][i]<=r[i]) f[1<<i][i]=max(L[i],a[n-1][i])+t[i]; } int ans=0; for(int i=1;i<1<<m;i++) for(int j=0;j<m;j++) if (f[i][j]<=1e9&&(i&(1<<j))){ int s=0; for(int k=0;k<m;k++) if (i&(1<<k)) s++; ans=max(ans,s); for(int k=0;k<m;k++) if (!(i&(1<<k))&&f[i][j]+a[j][k]<=r[k]) f[i^(1<<k)][k]=min(f[i^(1<<k)][k],max(L[k],f[i][j]+a[j][k])+t[k]); } return ans; }