本人A了三个，只有800KB
看题解大佬全是2000多KB
蒟蒻我有点懵逼
附上我的评测记录
[](https://www.luogu.org/record/show?rid=12928479)
by 陌尘缘_怜 @ 2018-11-01 23:48:22
@[陌尘缘_怜](/space/show?uid=67984) 两种可能。
* dfs爆栈需要优化
* 二维vector爆炸
by disangan233 @ 2018-11-02 00:23:34
剪枝然后$10000+$的$vector$会炸
by Quank123Wip @ 2018-11-02 06:14:31
@[Esport_P1ayErX](/space/show?uid=73552)
vector 会炸？？？
by 陌尘缘_怜 @ 2018-11-02 18:09:12
@[disangan233](/space/show?uid=72679)
谢谢，第一次知道vector会炸
by 陌尘缘_怜 @ 2018-11-02 18:10:21
@[陌尘缘_怜](/space/show?uid=67984) 10000+个vector啊
by Quank123Wip @ 2018-11-03 11:14:06
@[Esport_P1ayErX](/space/show?uid=73552)
可是蒟蒻我的另一题4568飞行路线由于需要分层建图开了100,000的vector却AC了？
```cpp
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
void Read(int &x);
void Write(int x);
struct edge{
int ks,ns,nt,kt,l;
};
edge e[5000005];
int n,m,k,es,et;
vector<int> v[12][10005];
struct node{
int xk,x;
int di;
bool operator < (const node w) const
{
return di>w.di;
}
};
priority_queue<node> q;
bool b[12][10005];
int dis[15][10005];
void dij()
{
memset(b,false,sizeof(b));
memset(dis,0x3f,sizeof(dis));
q.push((node){0,es,0});
dis[0][es]=0;
while(!q.empty())
{
node w=q.top();//cout<<"*";
q.pop();
if(b[w.xk][w.x]) continue;
b[w.xk][w.x]=true;
for(int i=0,len=v[w.xk][w.x].size();i<len;i++)
{
int t=e[v[w.xk][w.x][i]].nt;
int tk=e[v[w.xk][w.x][i]].kt;
if(dis[tk][t]>dis[w.xk][w.x]+e[v[w.xk][w.x][i]].l)
{
dis[tk][t]=dis[w.xk][w.x]+e[v[w.xk][w.x][i]].l;
q.push((node){tk,t,dis[tk][t]});
}
}
}
Write(dis[k][et]);
}
int main()
{
Read(n),Read(m),Read(k);//建k+1层
//点从0 到 n-1
Read(es),Read(et);
int ss,tt,ll;
int j=0;
for(int i=1;i<=m;i++)
{
Read(ss),Read(tt),Read(ll);
for(int kk=0;kk<=k;kk++)//各层建边
{
v[kk][ss].push_back(++j),e[j].ns=ss,e[j].nt=tt,e[j].l=ll,e[j].ks=kk,e[j].kt=kk;
v[kk][tt].push_back(++j),e[j].ns=tt,e[j].nt=ss,e[j].l=ll,e[j].ks=kk,e[j].kt=kk;
}
for(int kk=1;kk<=k;kk++)//从kk-1层到kk层建边
{
v[kk-1][ss].push_back(++j),e[j].ns=ss,e[j].nt=tt,e[j].l=0,e[j].ks=kk-1,e[j].kt=kk;
v[kk-1][tt].push_back(++j),e[j].ns=tt,e[j].nt=ss,e[j].l=0,e[j].ks=kk-1,e[j].kt=kk;
}
}
dij();
return 0;
}
void Read(int &x)
{
int i=1;
x=0;
char c=getchar();
while(c<'0' or c>'9')
{
if(c=='-') i=-1;
c=getchar();
}
while(c>='0' and c<='9')
{
x=x*10+(c-'0');
c=getchar();
}
x*=i;
}
void Write(int x)
{
if(x<0)
{
putchar('-');
x=-1*x;
}
if(x>9) Write(x/10);
putchar(x%10+'0');
}
```
by 陌尘缘_怜 @ 2018-11-03 13:45:32
@[Esport_P1ayErX](/space/show?uid=73552)
而且vector不应该是动态数组么，内存是比邻接表小的不是么，除了会慢点不是么？？
by 陌尘缘_怜 @ 2018-11-03 13:48:25