Uva(11820)(Flying to Fredericton

链接：https://vjudge.net/problem/UVA-11280
思路：dijkstra和动态规划结合的题目，其中有个点被坑的不要不要的，如果给的次数大于城市的数目则要初始化为n-1，因为最多转机n-1次不这样处理的话就会一直WA，经验教训啊！！！！！
代码：

#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<map>
#include<iostream>
using namespace std;

const int INF = 0x3f3f3f3f;
const int maxn = 105;
int t,n,m;
map<string,int> maple;

struct edge{
    int from,to,dist;
    edge(){}
    edge(int f,int t,int d):from(f),to(t),dist(d){}
};

struct node{
    int id;int s;int cost;
    node(){}
    node(int i,int ss,int c):id(i),s(ss),cost(c){}
    bool operator<(const node & q)const{
        return cost>q.cost;
    }
};

struct Dijskstra{
    int n,m;
    vector<edge> edges;
    vector<int> G[maxn];
    int d[maxn][maxn];
     
void init(int n){
    this->n = n;
    for(int i=0;i<=n;++i)G[i].clear();
        edges.clear();
}

void addedge(int from,int to,int cost){
    edges.push_back(edge(from,to,cost));
    m = edges.size();
    G[from].push_back(m-1);
}

int dijskstra(int s){
for(int i=0;i<=n;i++){
    for(int j=0;j<=103;j++){
        d[i][j] = INF;
    }
}
d[0][s+1] = 0;
priority_queue<node> qq;
qq.push(node(0,s+1,0));
while(!qq.empty()){
    node p = qq.top();
    qq.pop();
    int u = p.id;
    int ss = p.s;
    if(d[u][ss]<p.cost)continue;
    for(int i=0;i<G[u].size();i++){
        edge &e = edges[G[u][i]];
        if(d[e.to][ss-1]>d[u][ss]+e.dist&&ss>0){//动态规划！
            d[e.to][ss-1] = d[u][ss] + e.dist;
            qq.push(node(e.to,ss-1,d[e.to][ss-1]));
        }
    }
}
int ans = INF;
for(int i=0;i<=min(n-1,s+1);i++){
    ans = min(ans,d[n-1][i]);
}
return ans;
}
}solver;

int main(){
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    int kase  = 0;
    scanf("%d",&t);
    while(t--){
        if(kase)printf("\n");
        maple.clear();
        scanf("%d",&n);
        solver.init(n);
        string now,noww;
        for(int i=0;i<n;i++){
            cin>>now;
            maple[now] = i;
        }
        scanf("%d",&m);
        int c;
        for(int i=0;i<m;i++){
         cin>>now>>noww>>c;
         solver.addedge(maple[now],maple[noww],c);
        }
        printf("Scenario #%d\n",++kase);
        int q;
        scanf("%d",&q);
        while(q--){
            scanf("%d",&c);
            if(c>n-1)c = n-1;//鲁棒性！！！！！！！！！1
             int res = solver.dijskstra(c);
            if(res==INF)printf("No satisfactory flights\n");
            else printf("Total cost of flight(s) is $%d\n",res);
        }
    }
    return 0;
}