John的农场是一张 N*N 的方格图，贝茜住在左上角（1,1），John住在右下角（N,N）。
现在贝茜要去拜访John，每次都只能往四周与之相邻的方格走，并且每走一步消耗时间 T。
同时贝茜每走三步就要停下来在当前方格吃草，在每个方格吃草的用时是固定的，为 H[i][j]。
John想知道贝茜最少要多久才能到达John的家。
跑一遍djstl。
#include<bits/stdc++.h>
using namespace std;
constexpr int inf = 1e9;
int n, t, h[105][105],d[105][105][5];
int dx[] = {1,-1,0,0,},dy[] = {0,0,1,-1};
struct Pr{
int a, b;
};
queue<Pr> q,q1;
int main(){
cin>>n>>t;
for(int i = 1;i <= n;i++)
for(int j = 1;j <= n;j++){
cin>>h[i][j];
}
for(int i = 0;i < 105;i++){
for(int j = 0;j < 105;j++){
d[i][j][0] = d[i][j][1] = d[i][j][2] = d[i][j][3] = d[i][j][4] = inf;
}
}
q.push({1,1}),q1.push({0,0}),d[1][1][0] = 0;
while(!q.empty()){
for(int i = 0;i < 4;i++){
int x = q.front().a + dx[i],y = q.front().b + dy[i];
if(x > 0 && x <= n && y > 0 && y <= n){
int s = (q1.front().a + 1) % 3,v = q1.front().b
+ t + (!s) * h[x][y];
if(v < d[x][y][s]){
q.push({x,y}),q1.push({s,v}),d[x][y][s] = v;
}
}
}
q.pop(), q1.pop();
}
cout<<min(d[n][n][0],min(d[n][n][1],d[n][n][2]));
}
给定一个完全图，已知两点之间的距离，以及通过某个点的时间（起点和终点不需要花费时间）。你需要回答一些询问，输出两点之间的最短路径，同时需要输出方案。如果有多个方案，输出字典序最小的方案。
数据范围极小，djstl，同时统计一下路径。
一个n点m边无向图，边权均为1，有k个询问
每次询问给出(s,t,d)，要求回答是否存在一条从s到t的路径，长度为d
路径不必是简单路(可以自交)
数据保证不存在自环
由于两个点路径距离为d，就一定存在距离为d+2的路径。所以分层图对每个点跑一边spfa求出每个点到其他点经过奇数路径和偶数路径的距离，然后就可以直接判了。
#include<bits/stdc++.h>
#define N 5005
#define INF 0x3f3f3f3f
using namespace std;
template<typename T>inline void read(T &a){
char c=getchar();T x=0,f=1;
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
a=f*x;
}
vector<int> t[N];
int n,m,k,tot,h[N];
bool vis[N],ans[1000005];
int dis[2][N];
struct query{
int u,v,w;
}q[1000005];
struct node{
int nex,to;
}edge[N<<1];
inline void add(int u,int v){
edge[++tot].nex=h[u];
edge[tot].to=v;
h[u]=tot;
}
inline void spfa(int s){
queue<int> Q;
for(int i=1;i<=n;i++)dis[0][i]=INF,dis[1][i]=INF,vis[i]=0;
Q.push(s);vis[s]=1;dis[0][s]=0;
while(!Q.empty()){
int x=Q.front();Q.pop();vis[x]=0;
for(int i=h[x];i;i=edge[i].nex){
int xx=edge[i].to,flg=0;
if(dis[0][x]!=INF){
if(dis[1][xx]>dis[0][x]+1)
dis[1][xx]=dis[0][x]+1,flg=1;
}
if(dis[1][x]!=INF){
if(dis[0][xx]>dis[1][x]+1)
dis[0][xx]=dis[1][x]+1,flg=1;
}
if(flg&&!vis[xx])Q.push(xx),vis[xx]=1;
}
}
}
int main(){
cin>>n>>m>>k;
for(int i=1,u,v;i<=m;i++){
read(u);read(v);
add(u,v);add(v,u);
}
for(int i=1;i<=k;i++){
read(q[i].u),read(q[i].v),read(q[i].w);
t[q[i].u].push_back(i);
}
for(int i=1;i<=n;i++){
if(!t[i].size())continue;
spfa(i);
for(int j=0;j<(int)t[i].size();j++){
int o=t[i][j];
int num=q[o].w%2;
if(q[o].w>=dis[num][q[o].v]&&h[i])ans[o]=1;
}
}
for(int i=1;i<=k;i++)
if(ans[i])printf("TAK\n");
else printf("NIE\n");
return 0;
}