HDU 4725 The Shortest Path in Nya Graph（最短路建边）题解

题意：给你n个点，m条无向边，每个点都属于一个层，相邻层的任意点都能花费C到另一层任意点，问你1到n最小路径

思路：没理解题意，以为每一层一个点，题目给的是第i个点的层数编号。这道题的难点在于建边，如果用最朴素的相邻层所有点互相连接，那么可能有5*10^4连5*10^4，复杂度O(n^2)。这里我们用拆点（？大概），把每一层拆出一个点，作为每一层点和相邻层连接的中转站。这里要特别注意，同一层的点的距离不是0，所以我们建边不能全是无向边：

1.层与层无向边，权值C

2.层与同层点建单向边，权值0

2.点与相邻层单向边，权值C

这样，每个点都能通过每层拆出的点连接相邻层的点，而且同层的点的距离不为0。然而写完这些后我又TLE了...orz，把建边的vector邻接表改成手动建边，358ms过

代码：

#include<cstdio>

#include<set>

#include<cmath>

#include<stack>

#include<vector>

#include<queue>

#include<cstring>

#include<string>

#include<sstream>

#include<iostream>

#include<algorithm>

#define ll long long

using namespace std;

const int maxn = +;

const int INF = 0x3f3f3f3f;

struct Edge{

    int v,w,next;

}edge[*maxn];

bool vis[maxn];

int dis[maxn],head[maxn],tot;

void spfa(int start){

    memset(vis,false,sizeof(vis));

    memset(dis,INF,sizeof(dis));

    vis[start] = true;

    dis[start] = ;

    queue<int> q;

    while(!q.empty()) q.pop();

    q.push(start);

    while(!q.empty()){

        int u = q.front();

        q.pop();

        vis[u] = false;

        for(int i = head[u];i != -;i = edge[i].next){

            int v = edge[i].v;

            int w = edge[i].w;

            if(dis[v] > dis[u] + w){

                dis[v] = dis[u] + w;

                if(!vis[v]){

                    q.push(v);

                    vis[v] = true;

                }

            }

        }

    }

}

void addEdge(int u,int v,int w){

    edge[tot].v = v;

    edge[tot].w = w;

    edge[tot].next = head[u];

    head[u] = tot++;

}

int layer[maxn];

bool have[maxn];

int main(){

    int T;

    int n,m,C,Case = ;

    scanf("%d",&T);

    while(T--){

        scanf("%d%d%d",&n,&m,&C);

        tot = ;

        memset(head,-,sizeof(head));

        memset(have,false,sizeof(have));

        for(int i =  ;i <= n;i++){

            scanf("%d",&layer[i]);

            have[layer[i]] = true;

        }

        for(int i = ;i < n;i++){   //层层建边

            if(have[i] && have[i + ]){

                addEdge(n + i,n + i + ,C);

                addEdge(n + i + ,n + i,C);

            }

        }

        for(int i = ;i <= n;i++){  //层点建边 相邻层点建边

            addEdge(n + layer[i],i,);

            if(layer[i] > )

                addEdge(i,n + layer[i] - ,C);

            if(layer[i] < n)

                addEdge(i,n + layer[i] + ,C);

        }

        while(m--){

            int u,v,w;

            scanf("%d%d%d",&u,&v,&w);

            addEdge(u,v,w);

            addEdge(v,u,w);

        }

        spfa();

        if(dis[n] == INF){

            printf("Case #%d: -1\n",Case++);

        }

        else{

            printf("Case #%d: %d\n",Case++,dis[n]);

        }

    }

    return ;

}