HDU - 4725 The Shortest Path in Nya Graph 最短路

題意：

給若幹點，分布于若幹層，同層的點是不可以直接到達的，鄰層的點可以互相到達，花費為c，同時給了若幹無向路，求1到n的最小花費

分析：

題目難點在于建圖，要将層抽象為邊的關系，于是我們可以假設出2 * n個點，每層一個進點，一個出點，進點有到該層的實點和相鄰層的出點到它的有向路，出點反之

本題去了一個坑點，題意上相鄰層若沒點是不可互通的，也就是說我們需要考慮一個無點層兩側的點的關系，但是題目所給的輸入時排除了這種情況的

另外因為是稠密圖，是以迪傑斯特拉+堆優化的效率更高，spfa+堆優化勉強能過。

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e6;
const int inf=0x3f3f3f3f;

int head[maxn];
int tot;

struct Edge{
    int to,w;
    int nxt;
    Edge(){}
    Edge(int v,int w):to(v),w(w){}
}edge[maxn];

void addedge(int u,int v,int w){
    edge[tot].to=v;
    edge[tot].w=w;
    edge[tot].nxt=head[u];
    head[u]=tot++;
}

struct qnode{
    int v,c;
    qnode(int v=0,int c=0):v(v),c(c){}
    bool operator < (const qnode &r) const {
        return c>r.c;
    }
};

bool vis[maxn];
int dis[maxn];

void dijkstra(int s,int n){
    memset(vis,0,sizeof vis);
    for(int i=1;i<=n;i++){
        dis[i]=inf;
    }
    priority_queue<qnode> q;
    dis[s]=0;
    q.push(qnode(s,0));
    qnode tmp;
    while(!q.empty()){
        tmp=q.top();
        q.pop();
        int u=tmp.v;
        if(vis[u]) continue;
        vis[u]=true;
        for(int i=head[u];i!=-1;i=edge[i].nxt){
            int v=edge[i].to;
            int w=edge[i].w;
            if(!vis[v]&&dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                q.push(qnode(v,dis[v]));
            }
        }
    }
}

int main(){
    int T;
    scanf("%d",&T);
    for(int cs=1;cs<=T;cs++){
        int n,m,c;
        scanf("%d%d%d",&n,&m,&c);
        memset(head,-1,sizeof head);
        tot=0;
        for(int i=1;i<=n;i++){
            int r;
            scanf("%d",&r);
            addedge(n+r,i,0);
            addedge(i,2*n+r,0);
        }
        while(m--){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            addedge(u,v,w);
            addedge(v,u,w);
        }
        for(int i=1;i<n;i++){
            addedge(n*2+i,n+i+1,c);
            addedge(n*2+i+1,n+i,c);
        }
        dijkstra(1,3*n);
        if(dis[n]==inf) dis[n]=-1;
        printf("Case #%d: %d\n",cs,dis[n]);
    }
    return 0;
}