题目原文
这一晚，TT 做了个美梦！
在梦中，TT 的愿望成真了，他成为了喵星的统领！喵星上有 N 个商业城市，编号 1 ～ N，其中 1 号城市是 TT 所在的城市，即首都。
喵星上共有 M 条有向道路供商业城市相互往来。但是随着喵星商业的日渐繁荣，有些道路变得非常拥挤。正在 TT 为之苦恼之时，他的魔法小猫咪提出了一个解决方案！TT 欣然接受并针对该方案颁布了一项新的政策。
具体政策如下：对每一个商业城市标记一个正整数，表示其繁荣程度，当每一只喵沿道路从一个商业城市走到另一个商业城市时，TT 都会收取它们（目的地繁荣程度 - 出发地繁荣程度）^ 3 的税。
TT 打算测试一下这项政策是否合理，因此他想知道从首都出发，走到其他城市至少要交多少的税，如果总金额小于 3 或者无法到达请悄咪咪地打出 '?'。
Input
第一行输入 T，表明共有 T 组数据。（1 <= T <= 50）
对于每一组数据，第一行输入 N，表示点的个数。（1 <= N <= 200）
第二行输入 N 个整数，表示 1 ～ N 点的权值 a[i]。（0 <= a[i] <= 20）
第三行输入 M，表示有向道路的条数。（0 <= M <= 100000）
接下来 M 行，每行有两个整数 A B，表示存在一条 A 到 B 的有向道路。
接下来给出一个整数 Q，表示询问个数。（0 <= Q <= 100000）
每一次询问给出一个 P，表示求 1 号点到 P 号点的最少税费。
Output
每个询问输出一行，如果不可达或税费小于 3 则输出 '?'。
Sample Input
2
5
6 7 8 9 10
6
1 2
2 3
3 4
1 5
5 4
4 5
2
4
5
10
1 2 4 4 5 6 7 8 9 10
10
1 2
2 3
3 1
1 4
4 5
5 6
6 7
7 8
8 9
9 10
2
3 10
Sample Output
Case 1:
3
4
Case 2:
?
?
解题思路
本题给出各端点税收，求端点间的权值，此时权值可能出现负值，如果单纯使用SPFA可能会进入负环，从而进入死循环，因此需要在SPFA的基础上判断负环（如果在C点前的A，B出现负环，则A、B、C点总金额小于3），故新增一个数组对每一个节点访问次数进行标记，如果超过总数n，则出现负环，则从第一个被访问过n次的节点继续往后进行bfs查找（查找到的点均为总金额小于三的点），并用vis[]数组标记，由于各点的初始到达金额均被赋值为较大值，且d[0]未被更改，因此判断q点是否能够输出最小金额，只需判断d[q]大于等于3且未被vis[]数组标记（金额小于3），且值不等于d0即可。
实现代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<cmath>
using namespace std;
const int maxn=210;
const int maxm=100010;
const int maxq=100010;
int n,m;
int a[maxn];
int h[maxn];
int d[maxn];
bool in[maxn];
bool vis[maxn];//bfs
int count[maxn];//标记节点入队几次，判断负环位置
struct Edge{
int x,y,w,next;
}e[maxm*2];
void bfs(int y){
queue<int>p;
p.push(y);
vis[y]=1;
while(!p.empty()){
int x=p.front();
p.pop();
for(int i=h[x];i;i=e[i].next)
{
int t=e[i].y;
if(!vis[t]){
p.push(t);
vis[t]=1;
}
}
}
}
void SPFA(int st){
memset(in,0,sizeof(in));
memset(d,0x3f,sizeof(d));
memset(vis,0,sizeof(vis));
memset(count,0,sizeof(count)); //记得清空
queue<int>q;
d[st]=0;
q.push(st);
in[st]=1;
count[st]++;
while(!q.empty()){
int x=q.front();
q.pop();
if(vis[x]){
continue;
}
in[x]=0;
//遍历以x为起始节点的路径
for(int i=h[x];i;i=e[i].next){
int y=e[i].y,w=e[i].w;
if(w+d[x]<d[y]){
d[y]=d[x]+w;
if(!in[y]){
q.push(y);
in[y]=1;
count[y]++;
if(count[y]>n)
bfs(y);//需要继续找与x后面的点
}
}
}
}
}
void makeE(int x,int y,int w,int cnt){
e[cnt]={x,y,w,h[x]};
h[x]=cnt;
}
int main(){
int t,q;
cin>>t;
int x,y,w,num=0;
while(t--){
num++;
cin>>n;
memset(h,0,sizeof(h));
//memset(a,0,sizeof(a));
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
cin>>m;
int cnt=0;
for(int i=1;i<=m;i++)
{
cin>>x>>y;
makeE(x,y,pow(a[y]-a[x],3),++cnt);// e[i]={x,y,a[y]-a[x],}
}
SPFA(1);
cin>>q;
int Q;
cout<<"Case "<<num<<":"<<endl;
for(int i=1;i<=q;i++)
{
cin>>Q;
if(d[Q]>=3&&!vis[Q]&&d[Q]!=d[0])
cout<<d[Q]<<endl;
else
cout<<"?"<<endl;
}
}
return 0;
}
小结
在SPFA中调用bfs算法是，应该在SPFA中的遍历循环中套用，避免出现负环的端点后有不止一条分支。
