题目数据有锅，一下午错了二十多发。。。
送外卖2
题目描述上给的范围是n<=10
实测存在n>15的数据
ac代码与报错（居然不是段错误）代码之间只有开数组大小有区别
#include<bits/stdc++.h>
#define rep(i,n) for(int i=1;i<=n;i++)
#define rwp(i,l,r) for(int i=l;i<=r;i++)
#define int long long
#define endl '\n'
#define pp push_back
#define pr pair<int,int>
#define x first
#define y second
using namespace std;
const int N=2e5+5;
const int mod=1e9+7;
int x,y,z,n,m,k,t;
string s;
int trs,w,_trans;
int Dis[25][25],Dp[30][60000];
int Bit[30],Val[60000];
struct node {
int u,v,l,r;
node(){}
void input() {
cin>>u>>v>>l>>r;
}
} no[20];
void init() {
cin>>n>>m>>trs;
rep(i,n) rep(j,n) if(i^j) Dis[i][j]=mod;
rep(i,m) {
cin>>x>>y>>w;
Dis[x][y]=min(Dis[x][y],w);
}
rep(i,n) rep(j,n) rep(k,n) {
Dis[j][k]=min(Dis[j][k],Dis[j][i]+Dis[i][k]);
}
rep(i,trs) no[i].input();
Bit[1]=1;
for(int i=2;i<=trs;i++)
Bit[i]=Bit[i-1]*3;
_trans=Bit[trs]*3;
for(int trans=0;trans<_trans;trans++) {
Val[trans]=Val[trans/3];
if(trans%3==2) Val[trans]++;
//cout<<Val[trans]<<endl;
}
rep(i,n) rep(trans,_trans) Dp[i][trans-1]=mod;
Dp[1][0]=0;
}
void make_trans_1(int i,int trans) {
int v=no[i].v;
for(int u=1;u<=n;u++) {
int t=Dp[u][trans-Bit[i]];
t=max(t+Dis[u][no[i].u],no[i].l);
if(t>no[i].r) continue;
Dp[no[i].u][trans]=min(Dp[no[i].u][trans],t);
}
}
int ans=0;
void make_trans_2(int i,int trans) {
int v=no[i].v;
for(int u=1;u<=n;u++) {
int t=Dp[u][trans-Bit[i]];
t+=Dis[u][v];
if(t>no[i].r) continue;
Dp[v][trans]=min(Dp[v][trans],t);
ans=max(ans,Val[trans]);
}
}
void solve() {
init();
for(int trans=0;trans<_trans;trans++) {
int tmp=trans;
rep(i,trs) {
int t=tmp%3;
if(t==1) make_trans_1(i,trans);
if(t==2) make_trans_2(i,trans);
tmp/=3;
}
}
cout<<ans<<endl;
}
signed main() {
ios::sync_with_stdio(false);
//int T;cin>>T;
//while(T--)
solve();
}