题目大意：一些节点分布在不同的层上，已知相邻的层可以往来距离为c，在给你一些已知的边，问你点1-n的最短路
分析：越往后做，越觉得最短路的考点已经不是spfa算法还是dijkscar算法了，而是图形的创建，你脑海里既要有他给你描绘出的问题场景图，也要有适应算法而建造的图模型，其实这个题有很多的建图方式，看你怎么想了，只能说我的模型化思想还没有完全好，这个图在我脑子里已经TLE了，看了看别人的题目大意又重整旗鼓模拟了一下~~
就是你把一个层就看做一个点，一开始的输入会告诉你每一个点具体在第几层，你可以标记一下，哪些层出现过（TLE点1：你当然可以不标记，然后给每一个相邻的层建边，但是spfa就会麻烦了，tle，因为很可能你会在没有点的层上乱逛）
for(int i = 1;i <= n;i++)
{
scanf("%d",&flor[i]);//i点在l层
vis[flor[i]] = 1;
}
for(int i = 1;i < n;i++)
{
if(vis[i] && vis[i + 1])
{
add(i + n,i + n + 1,c);
add(i + n + 1,i + n,c);
}
}
层层间的路建好了，就剩下点和层的了，（TLE点2：一般都会想的是，把点和它所在的层一一连接起来就好了也就是i 和 n + flor[i]），其实这是一条比较费的路，只会徒增加时间，要知道spfa的队列限制了它一步一步更新最短路，所以你的结点越多，也就会越慢，所以直接跨越一个结点，连接i和i层所在的上下层
剩下的就真的是默写spfa了
#include <iostream>
#include <queue>
#include <cstdio>
#include <string.h>
#include <vector>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn = 3e5 + 3e2;
struct node
{
int to,cost,pre;
// node(int t,int c,int p):to(t),cost(c),pre(p){}
}edge[maxn * 10];
//vector<node> edge[maxn];
int n;
int d[maxn];
int vis[maxn];
int id[maxn];
int cnt;int flor[maxn];
queue<int>q;
void init()
{
// memset(vis,0,sizeof(vis));
// memset(id,-1,sizeof(id));
for(int i = 1;i <= 3*n;i++)
{
// edge[i].clear();
d[i] = inf;
vis[i] = 0;
id[i] = -1;
}
memset(flor,0,sizeof(flor));
cnt = 0;
while(!q.empty())q.pop();
}
void add(int from,int to,int cost)
{
// edge[from].push_back(node(to,cost));
edge[cnt].to = to;
edge[cnt].cost = cost;
edge[cnt].pre = id[from];
id[from] = cnt++;
}
void spfa(int s)
{
memset(vis,0,sizeof(vis));
d[s] = 0;
vis[s] = 1;
q.push(s);
while(q.size())
{
int now = q.front();q.pop();vis[now] = 0;
// for(int i = 0;i < edge[now].size();i++)
for(int i = id[now];~i;i = edge[i].pre)
{
// cout<<i<<endl;
// int to = edge[now][i].to;
// int cost = edge[now][i].cost;
int to = edge[i].to;
int cost = edge[i].cost;
if(d[to] > d[now] + cost)
{
d[to] = d[now] + cost;
if(!vis[to])
{
vis[to] = 1;
q.push(to);
}
}
}
}
}
int main()
{
int t,m,c,a,b,x;
scanf("%d",&t);
int cas = 1;
while(t--)
{
scanf("%d%d%d",&n,&m,&c);
init();
for(int i = 1;i <= n;i++)
{
scanf("%d",&flor[i]);//i点在l层
vis[flor[i]] = 1;
}
for(int i = 1;i < n;i++)
{
if(vis[i] && vis[i + 1])
{
add(i + n,i + n + 1,c);
add(i + n + 1,i + n,c);
}
}
for(int i = 1;i <= n;i++)
{
add(n + flor[i],i,0);
if(flor[i] > 1)
add(i,n + flor[i] - 1,c);
if(flor[i] < n)
add(i,n + flor[i] + 1,c);
}
while(m--)
{
scanf("%d%d%d",&a,&b,&x);
add(a,b,x);
add(b,a,x);
}
spfa(1);
if(d[n] == inf)d[n] = -1;
printf("Case #%d: %d
",cas++,d[n]);
}
return 0;
}
WA了11次！思路很重要~！