題目原文
這一晚，TT 做了個(gè)美夢(mèng)！
在夢(mèng)中，TT 的愿望成真了，他成為了喵星的統(tǒng)領(lǐng)！喵星上有 N 個(gè)商業(yè)城市，編號(hào) 1 ～ N，其中 1 號(hào)城市是 TT 所在的城市，即首都。
喵星上共有 M 條有向道路供商業(yè)城市相互往來(lái)。但是隨著喵星商業(yè)的日漸繁榮，有些道路變得非常擁擠。正在 TT 為之苦惱之時(shí)，他的魔法小貓咪提出了一個(gè)解決方案！TT 欣然接受并針對(duì)該方案頒布了一項(xiàng)新的政策。
具體政策如下：對(duì)每一個(gè)商業(yè)城市標(biāo)記一個(gè)正整數(shù)，表示其繁榮程度，當(dāng)每一只喵沿道路從一個(gè)商業(yè)城市走到另一個(gè)商業(yè)城市時(shí)，TT 都會(huì)收取它們（目的地繁榮程度 - 出發(fā)地繁榮程度）^ 3 的稅。
TT 打算測(cè)試一下這項(xiàng)政策是否合理，因此他想知道從首都出發(fā)，走到其他城市至少要交多少的稅，如果總金額小于 3 或者無(wú)法到達(dá)請(qǐng)悄咪咪地打出 '?'。
Input
第一行輸入 T，表明共有 T 組數(shù)據(jù)。（1 <= T <= 50）
對(duì)于每一組數(shù)據(jù)，第一行輸入 N，表示點(diǎn)的個(gè)數(shù)。（1 <= N <= 200）
第二行輸入 N 個(gè)整數(shù)，表示 1 ～ N 點(diǎn)的權(quán)值 a[i]。（0 <= a[i] <= 20）
第三行輸入 M，表示有向道路的條數(shù)。（0 <= M <= 100000）
接下來(lái) M 行，每行有兩個(gè)整數(shù) A B，表示存在一條 A 到 B 的有向道路。
接下來(lái)給出一個(gè)整數(shù) Q，表示詢(xún)問(wèn)個(gè)數(shù)。（0 <= Q <= 100000）
每一次詢(xún)問(wèn)給出一個(gè) P，表示求 1 號(hào)點(diǎn)到 P 號(hào)點(diǎn)的最少稅費(fèi)。
Output
每個(gè)詢(xún)問(wèn)輸出一行，如果不可達(dá)或稅費(fèi)小于 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:
?
?
解題思路
本題給出各端點(diǎn)稅收，求端點(diǎn)間的權(quán)值，此時(shí)權(quán)值可能出現(xiàn)負(fù)值，如果單純使用SPFA可能會(huì)進(jìn)入負(fù)環(huán)，從而進(jìn)入死循環(huán)，因此需要在SPFA的基礎(chǔ)上判斷負(fù)環(huán)（如果在C點(diǎn)前的A，B出現(xiàn)負(fù)環(huán)，則A、B、C點(diǎn)總金額小于3），故新增一個(gè)數(shù)組對(duì)每一個(gè)節(jié)點(diǎn)訪(fǎng)問(wèn)次數(shù)進(jìn)行標(biāo)記，如果超過(guò)總數(shù)n，則出現(xiàn)負(fù)環(huán)，則從第一個(gè)被訪(fǎng)問(wèn)過(guò)n次的節(jié)點(diǎn)繼續(xù)往后進(jìn)行bfs查找（查找到的點(diǎn)均為總金額小于三的點(diǎn)），并用vis[]數(shù)組標(biāo)記，由于各點(diǎn)的初始到達(dá)金額均被賦值為較大值，且d[0]未被更改，因此判斷q點(diǎn)是否能夠輸出最小金額，只需判斷d[q]大于等于3且未被vis[]數(shù)組標(biāo)記（金額小于3），且值不等于d0即可。
實(shí)現(xiàn)代碼
#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];//標(biāo)記節(jié)點(diǎn)入隊(duì)幾次，判斷負(fù)環(huán)位置
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為起始節(jié)點(diǎn)的路徑
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ù)找與x后面的點(diǎn)
}
}
}
}
}
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;
}
小結(jié)
在SPFA中調(diào)用bfs算法是，應(yīng)該在SPFA中的遍歷循環(huán)中套用，避免出現(xiàn)負(fù)環(huán)的端點(diǎn)后有不止一條分支。
