Submission #1294886

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define int long long
int dp[16][1<<16];
signed main(){
  int n,m,l,t,s;
  while(cin>>n>>m>>l>>s>>t,n){
    s--;
    int a[m],b[m],c[m];
    for(int i=0;i<m;i++) cin>>a[i]>>b[i]>>c[i];
    int d[l],e[l];
    for(int i=0;i<l;i++) cin>>d[i]>>e[i];
    int INF=1LL<<55LL;
    int g[n][n];
    for(int i=0;i<n;i++)
      for(int j=0;j<n;j++)
	g[i][j]=INF*(i!=j);
    for(int i=0;i<m;i++){
      a[i]--;b[i]--;
      g[a[i]][b[i]]=g[b[i]][a[i]]=c[i];
    }
    for(int k=0;k<n;k++)
      for(int i=0;i<n;i++)
	for(int j=0;j<n;j++)
	  g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
    map<int,int> mi;
    for(int i=0;i<l;i++){
      d[i]--;
      mi[d[i]]=i;
    }
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<l;i++)
      dp[i][1<<i]=g[s][d[i]]+e[i];
    int ans=0;
    for(int b=0;b<(1<<l);b++){
      for(int i=0;i<l;i++){
	if(dp[i][b]<0||dp[i][b]>t) continue;
	//cout<<i<<" "<<b<<endl;
	if(dp[i][b]+g[d[i]][s]<=t)
	  ans=max(ans,(int)__builtin_popcountll(b));
	for(int j=0;j<l;j++){
	  if((b>>j)&1) continue;
	  if(dp[j][b+(1<<j)]<0||dp[j][b+(1<<j)]>dp[i][b]+g[d[i]][d[j]]+e[j])
	    dp[j][b+(1<<j)]=dp[i][b]+g[d[i]][d[j]]+e[j];
	}
      }
    }
    cout<<ans<<endl;
  }
  return 0;
}

Submission Info

Judge Result