HDU4725(The Shortest Path in Nya

链接：https://vjudge.net/problem/HDU-4725
思路：题意是在普通最短路中，每个点有个对应的层次，相邻层次间的不同可以花代价c进行移动，求1-n的最短路。所以如何建图成为了一个关键。为了能够将不同层次的点之间花代价表示出来，不妨每个层次建立一个两个虚点，一个虚点表示从实点出来的，另一个表示要进入实点的，然后将每个实点与对应的两个虚点建立对应的两条边（由实点到出去的虚点，由另一个虚点到实点），然后相邻层次的虚点的出点和入点对应连接一条代价为c的边（注意要判断两个层次都必须有点存在才连，否则入1，3层次有点，2层次无点，则1无法到3），建图后跑一边最短路即可（spfa用优先队列优化一下）
代码：

#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
#include<algorithm>
#include<functional>
using namespace std;

const int maxn = 3e5+10;//一实点两虚点，总共三倍
int n,m,c,t;

typedef pair<int,int> P;

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

struct SPFA{
    int n,m;
    vector<edge> edges;
    vector<int> G[maxn];
    int d[maxn];
    int p[maxn];
    int f[maxn];
    int vis[maxn];
    int inq[maxn];
    int cnt[maxn];

    void init(int n){
     this->n = n;
     for(int i=0;i<=n;i++)G[i].clear();
        edges.clear();
         memset(vis,0,sizeof(vis));
    }

    void addedge(int from,int to,int dist){
        edges.push_back(edge(from,to,dist));
        m = edges.size();
        G[from].push_back(m-1);//放入的是edges中的编号
    }

    void spfa(int s){
        priority_queue<int,vector<int>,greater<int> > Q;//优先队列优化
        memset(inq,0,sizeof(inq));
        memset(cnt,0,sizeof(cnt));
        for(int i=0;i<n;i++){
            d[i] = 0x3f3f3f3f;
        }
        d[s] = 0;
        Q.push(s);
        while(!Q.empty()){
            int u = Q.top();
            Q.pop();
            inq[u] = false;
            for(int i=0;i<G[u].size();i++){
                edge& e = edges[G[u][i]];
                if(d[e.to]>d[u]+e.dist){
                    d[e.to] = d[u] + e.dist;
                    p[e.to] = u;
                    if(!inq[e.to]){
                        Q.push(e.to);
                        inq[e.to] = true;
                        if(++cnt[e.to]>n){                      
                            return ;
                        }
                    }
                }
            }
        }
    }

    void output(int s,int e,vector<int>& path){
        int pos=e;
        while(1){
            path.push_back(pos);
            if(pos==s) break;
            pos=p[pos];
        }
    }
}solver;

int main(){
    int kase = 0;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d",&n,&m,&c);
        solver.init(3*n);
        int now;
        for(int i=0;i<n;i++){
            scanf("%d",&now);
            solver.f[i] = now-1;
            solver.vis[now-1+n] = 1;//该层次有点存在，标记
        }
        for(int i=0;i<n;i++){
            solver.addedge(i,n+solver.f[i],0);//实点到出去的虚点
            solver.addedge(solver.f[i]+2*n,i,0);//进入的虚点到实点
        }
        for(int i=1;i<n;i++){
            if(solver.vis[i+n-1]&&solver.vis[i+n]){//相邻层次存在点，则连边
            solver.addedge(i+n-1,i+2*n,c);
            solver.addedge(i+n,i+2*n-1,c);
            }
        }
        for(int i=0;i<m;i++){
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            a--;
            b--;
            solver.addedge(a,b,c);
            solver.addedge(b,a,c);
        }
        solver.spfa(0);
        if(solver.d[n-1]==0x3f3f3f3f)printf("Case #%d: -1\n",++kase);
        else printf("Case #%d: %d\n",++kase,solver.d[n-1]);
    }    
    return 0;
}