HDU 4725 The Shortest Path in Nya Graph

貌似是卡spfa的，但薛昊说slf优化一下也可以过
个人感觉写的非常崩溃……用数组实现队列的时候是WA，stl实现就是tle，我觉得这很可能是空间上的问题。因为最近数组大小开错不停wa不停tle的情况太多了……
看很多题解都是dijkstra实现的。改了一下直接A了

题意：
美团初赛城市群的原题……上次没写出来，碰到原题真的是内心崩溃。
简单说，在一张图的基础上，每个节点都会属于一个 “ 层 ” ，每个相邻的 “ 层 ” 中的节点都相互可达，问 1 到 n 的最短距离。

思路：
对 “ 层 ” 建立源点与汇点，对于每个层里面的每个点，源点到点 ，点到汇点的距离各为 0 。再对 “ 层 ” 之间建边，点之间建边跑最短路即可。

AC Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

using namespace std;
const int maxn = 1e6 + 5;
const int inf = 0x3f3f3f3f;

int dis[maxn], head[maxn];
bool vis[maxn];
int n, m, c, idx;

struct node {
    int to;
    int nxt;
    int weight;
} edges[maxn];

struct qnode {
    int to;
    int weight;
    qnode(int _to = 0, int _weight = 0)
        : to(_to)
        , weight(_weight)
    {
    }
    bool operator<(const qnode& a) const
    {
        return weight > a.weight;
    }
};

priority_queue<qnode> que;

void Dijkstra(int n, int start) 
{
    memset(vis, false, sizeof(vis));
    for (int i = 1; i <=3* n; i++)
        dis[i] = inf;
    while (!que.empty())
        que.pop();
    dis[start] = 0;
    que.push(qnode(start, 0));
    qnode tmp;
    while (!que.empty()) {
        tmp = que.top();
        que.pop();
        int u = tmp.to;
        if (vis[u])
            continue;
        vis[u] = true;
        for (int id = head[u]; ~id; id = edges[id].nxt) {
            int v = edges[id].to;
            int cost = edges[id].weight;
            if (!vis[v] && dis[v] > dis[u] + cost) {
                dis[v] = dis[u] + cost;
                que.push(qnode(v, dis[v]));
            }
        }
    }
    printf("%d\n", dis[n] == inf ? -1 : dis[n]);
}

inline void addEdge(int u, int v, int w)
{
    edges[idx].to = v;
    edges[idx].weight = w;
    edges[idx].nxt = head[u];
    head[u] = idx++;
}

int main()
{
    int T, u, v, w, layer;
    scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        scanf("%d %d %d", &n, &m, &c);
        memset(head, -1, sizeof head);
        idx = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &layer);
            addEdge(n + layer * 2 - 1, i, 0);
            addEdge(i, n + 2 * layer, 0);
        }
        for (int i = 1; i < n; i++) {
            addEdge(n + 2 * i, n + 2 * i + 1, c);
            addEdge(n + 2 * i + 2, n + 2 * i - 1, c);
        }
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d", &u, &v, &w);
            addEdge(u, v, w);
            addEdge(v, u, w);
        }
        printf("Case #%d: ", cas);
        Dijkstra(n,1);
    }
    return 0;
}