(中等) HDU 4725 The Shortest Path in Nya Graph，Dijkstra+加点。

Description

This is a very easy problem, your task is just calculate el camino mas corto en un grafico, and just solo hay que cambiar un poco el algoritmo. If you do not understand a word of this paragraph, just move on.
The Nya graph is an undirected graph with "layers". Each node in the graph belongs to a layer, there are N nodes in total.
You can move from any node in layer x to any node in layer x + 1, with cost C, since the roads are bi-directional, moving from layer x + 1 to layer x is also allowed with the same cost.
Besides, there are M extra edges, each connecting a pair of node u and v, with cost w.
Help us calculate the shortest path from node 1 to node N.

 

　　题意就是求最短路问题，但是有一个层的概念，刚开始的时候是想着把相邻两层之间的每一点都再连一条边，但是这样的复杂度可以到达 n^2 ，比如在相邻两层上都有 n/2 个点。

　　然后百度了之后，发现是要增加点，表示每一层，这个点和同层的连边的边权为0，这样的话两层之间就只需要再加一条边，但是这样还有一个问题，就是同层点之间来往的话，应该是到达相邻的层然后再回来，所以需要在每一层增加两点，分别表示入的和出的。。。

　　还有一个坑点，就是如果某一层没有点的话，是不能与相邻层连线的。。。

 

代码如下：

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
    
using namespace std;

const int MaxN=100005*10;
const int MaxM=100005*10;
const int INF=10e9+7;

struct Edge
{
    int to,next,cost;
};

struct Node
{
    int v,val;

    Node(int _v=0,int _val=0):v(_v),val(_val) {}

    bool operator < (const Node &a) const
    {
        return val>a.val;
    }
};

Edge E[MaxM];
int head[MaxN],Ecou;

void init(int N)
{
    Ecou=0;

    for(int i=1;i<=N;++i)
        head[i]=-1;
}

void addEdge(int u,int v,int c)
{
    E[Ecou].to=v;
    E[Ecou].cost=c;
    E[Ecou].next=head[u];
    head[u]=Ecou++;
}

bool vis[MaxN];

void Dijkstra(int lowcost[],int N,int start)
{
    priority_queue <Node> que;
    Node temp;
    int u,v,c;
    int len;

    for(int i=1;i<=N;++i)
    {
        lowcost[i]=INF;
        vis[i]=0;
    }

    lowcost[start]=0;
    que.push(Node(start,0));

    while(!que.empty())
    {
        temp=que.top();
        que.pop();

        u=temp.v;
        
        if(vis[u])
            continue;

        vis[u]=1;
        
        for(int i=head[u];i!=-1;i=E[i].next)
        {
            v=E[i].to;
            c=E[i].cost;

            if(!vis[v] && lowcost[v]> lowcost[u]+c)
            {
                lowcost[v]=lowcost[u]+c;
                que.push(Node(v,lowcost[v]));
            }
        }
    }
}

int ans[MaxN];
bool have[MaxN];

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);

    int T;
    int N,M,C;
    int u,v,c;
    int cas=1;

    scanf("%d",&T);

    while(T--)
    {

        scanf("%d %d %d",&N,&M,&C);

        init(3*N);
        memset(have,0,sizeof(have));

        for(int i=1;i<=N;++i)
        {
            scanf("%d",&u);
            
            addEdge(i,N+2*u-1,0);
            addEdge(N+2*u,i,0);

            have[u]=1;
        }

        for(int i=1;i<N;++i)
            if(have[i] && have[i+1])
            {
                addEdge(N+2*i-1,N+2*(i+1),C);
                addEdge(N+2*(i+1)-1,N+2*i,C);
            }

        for(int i=1;i<=M;++i)
        {
            scanf("%d %d %d",&u,&v,&c);

            addEdge(u,v,c);
            addEdge(v,u,c);
        }

        Dijkstra(ans,3*N,1);

        printf("Case #%d: %d
",cas++,ans[N]==INF ? -1 : ans[N]);
    }

    return 0;
}