题目大意：
给出n（2<=n<=100)个城市之间的m（0<=m<=1000）条航线以及对应的机票价格，要求回答一些询问，每个询问是给出最大停留次数S，求从其实城市Calgary到终点城市Fredericton中途停留次数不超过s的最便宜的路程。
思路：
这题坑爹的是用城市名，不是直接编号了，嗯，map搞定之。
SPFA的变形，用二维数组dis[i][j]记录到顶点i步数为j的最短路径。
最后根据要求的s遍历一下即可~
坑爹的是s可能大于顶点数， 然后我初始化坑了一回QAQ
#include<cstdio>
#include<cstring>
#include<string>
#include<map>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;
const int MAXN=100+10;
const int MAXM=1000+10;
const int INF=99999999;
int head[MAXN],len,n,m,dis[MAXN][MAXN],vis[MAXN][MAXN];
struct edge
{
int to,val,next;
}e[MAXM];
void add(int from,int to,int val)
{
e[len].to=to;
e[len].val=val;
e[len].next=head[from];
head[from]=len++;
}
struct node
{
int id,cnt;
node(int x,int c){cnt=c; id=x;}
};
void spfa(int s,int target,int tol)
{
memset(vis,0,sizeof(vis));
for(int i=0;i<=n+1;i++) //n+1坑啊，WA到爆，检查一个多小时才发现！！！
for(int j=0;j<=n+1;j++)
dis[i][j]=INF;
queue<node> q;
q.push(node(s,0));
vis[s][0]=true;
dis[s][0]=0;
while(!q.empty())
{
node cur=q.front();
q.pop();
vis[cur.id][cur.cnt]=false;
for(int i=head[cur.id];i!=-1;i=e[i].next)
{
int id=e[i].to;
if(e[i].val + dis[cur.id][cur.cnt] < dis[id][cur.cnt+1])
{
dis[id][cur.cnt+1] = e[i].val + dis[cur.id][cur.cnt] ;
if(!vis[id][cur.cnt+1])
{
vis[id][cur.cnt+1]=true;
q.push(node(id,cur.cnt+1));
}
}
}
}
}
int main()
{
int T;
scanf("%d",&T);
for(int ri=1;ri<=T;ri++)
{
memset(head,-1,sizeof(head));
len=0;
map<string,int> name;
scanf("%d",&n);
string a,b;
for(int i=1;i<=n;i++)
{
cin>>a;
name[a]=i;
}
int cost;
scanf("%d",&m);
for(int i=0;i<m;i++)
{
cin>>a>>b>>cost;
add(name[a],name[b],cost);
}
int start=name["Calgary"],fin=name["Fredericton"];
int k,tolerate;
scanf("%d",&k);
if(ri!=1)
printf("\n");
spfa(start,fin,n+1);
printf("Scenario #%d\n",ri);
for(int i=0;i<k;i++)
{
scanf("%d",&tolerate);
tolerate= min(tolerate, n); //坑啊
int ans=INF;
for(int j=0;j<=tolerate+1;j++)
ans=min(dis[fin][j],ans);
if(ans!=INF)
printf("Total cost of flight(s) is $%d\n", ans);
else
printf("No satisfactory flights\n");
}
}
return 0;
}