C++14(g++5.4) 解法, 执行用时: 54ms, 内存消耗: 12648K, 提交时间: 2019-10-29 21:52:24

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll dis[30][30],dp[22][70000];
ll bit[30],st[20],to[20],l[20],r[20];
int main(){
	memset(dis,0x3f,sizeof(dis));
	memset(dp,0x3f,sizeof(dp));
	int n,m,q;
	cin>>n>>m>>q;
	for(int i=1;i<=m;i++){
		int u,v,c;
		cin>>u>>v>>c;
		dis[u][v]=min(dis[u][v],c*1ll);
	}
	for(int i=1;i<=n;i++)dis[i][i]=0;
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
			}
		}
	}
	bit[0]=1;
	for(int i=1;i<=12;i++)bit[i]=bit[i-1]*3;
	for(int i=0;i<q;i++)cin>>st[i]>>to[i]>>l[i]>>r[i];
	dp[1][0]=0;
	int ans=0;
	for(int state=0;state<bit[q];state++){
		for(int i=1;i<=n;i++){
			if(dp[i][state]>=0x3f3f3f3f)continue;
			int tot=0; 
			for(int j=0;j<q;j++){
				int tmp=(state/bit[j])%3;
				if(tmp==0){
					dp[st[j]][state+bit[j]]=min(dp[st[j]][state+bit[j]],max(dp[i][state]+dis[i][st[j]],l[j]*1ll));
				}
				else if(tmp==1){
					if(dp[i][state]+dis[i][to[j]]<=r[j]){
						dp[to[j]][state+bit[j]]=min(dp[to[j]][state+bit[j]],dp[i][state]+dis[i][to[j]]);
					}
				}
				else tot++;
			}
			ans=max(ans,tot);
		}
	}
	cout<<ans<<endl;
	return 0;
} 

C++11(clang++ 3.9) 解法, 执行用时: 29ms, 内存消耗: 5088K, 提交时间: 2020-08-03 10:35:39

#include<iostream>
#include<cstdio>
#define INF 0x3f3f3f3f
using namespace std;
int f[22][60000];
int d[22][22];
int n,m,q,s[20],t[20],l[20],r[20],th[30],next1;
int main()
{
	int i,j,k,ans=0;
	cin>>n>>m>>q;
	int u,v,c;
	for(i=1;i<=n;++i)
	for(j=1;j<=n;++j)
	if(i!=j)d[i][j]=INF;
	for(i=1;i<=m;++i)
	{
		cin>>u>>v>>c;
		d[u][v]=min(d[u][v],c);
	}
	for(i=1;i<=q;++i)
	cin>>s[i]>>t[i]>>l[i]>>r[i];
    for(k=1;k<=n;++k)
	for(i=1;i<=n;++i)
	for(j=1;j<=n;++j)
	d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
	th[1]=1;
	for(i=2;i<=q+1;++i)
	th[i]=th[i-1]*3;
	for(j=1;j<=n;++j)
	for(i=0;i<=th[q+1];++i)
	f[j][i]=INF;
	f[1][0]=0;
	for(j=0;j<th[q+1];++j)
	for(i=1;i<=n;++i)
	if(f[i][j]!=INF)
	{
		int cnt=0;
		for(k=1;k<=q;++k)
		{
			next1=j/th[k]%3;
			if(next1==0)f[s[k]][j+th[k]]=min(f[s[k]][j+th[k]],max(l[k],f[i][j]+d[i][s[k]]));
			else if(next1==1)
			{
				if(f[i][j]+d[i][t[k]]<=r[k])f[t[k]][j+th[k]]=min(f[t[k]][j+th[k]],f[i][j]+d[i][t[k]]);
			}
			else cnt++;
		}
		ans=max(ans,cnt);
	}
	cout<<ans<<endl;
}