题意
在一个图上给你n个从1到n的节点，求依次经过1到n的路径总长，有障碍格不能通过。
题解
宽搜最短路，询问n次
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define SF scanf
#define PF printf
#define PII pair<int,int>
#define MAXN 1010
#define MAXM 20
using namespace std;
int n,m,cnt,time,ma[MAXN][MAXN],w[4][2]={
{
1,0},{-1,0},{
0,1},{
0,-1}};
PII num[MAXM];
queue<PII > q;
int vis[MAXN][MAXN];
char c;
void read(){SF("%d%d%d",&n,&m,&cnt);for(int i=1;i<=n;i++){SF("\n");for(int j=1;j<=m;j++){SF("%c",&c);if(c=='X')ma[i][j]=1;else if(c=='S')num[0]=make_pair(i,j);else if(c>='1'&&c<='9')num[c-'0']=make_pair(i,j);}}
}
int check(int x,int y){if(x*y==0||x>n||y>m)return 0;if(vis[x][y]!=0||ma[x][y]!=0)return 0;return 1;
}
int ask(int stx,int sty,int edx,int edy){while(!q.empty())q.pop();memset(vis,0,sizeof vis);q.push(make_pair(stx,sty));vis[stx][sty]=1;while(!q.empty()){PII nex=q.front();q.pop();int x=nex.first;int y=nex.second;//PF("(%d %d %d)\n",x,y,ma[x][y]);if(x==edx&&y==edy)return vis[x][y]-1;for(int i=0;i<4;i++){int x1=x+w[i][0];int y1=y+w[i][1];if(check(x1,y1)){q.push(make_pair(x1,y1));vis[x1][y1]=vis[x][y]+1;}}}}
int main(){read();for(int i=1;i<=cnt;i++)time+=ask(num[i-1].first,num[i-1].second,num[i].first,num[i].second);PF("%d\n",time);
}