AcWing 383. 观光

题目传送门

#include 
using namespace std;
const int N = 1010;
const int M = 10010;

int n, m;      // n个节点，m条边
int d[N][2];   //拆点，因为每个点都要计算最短路和次短路，所以一个点看到两个点
int cnt[N][2]; //最短路和次短路的路线个数
bool st[N][2]; //一个st拆成两个
int S, F;      //起点和终点
struct Node {
    int dist; //用于Dijkstra中排序的最短距离
    int id;   //节点号
    int type; // 0:最短路，1：次短路
};
//小顶堆，结构体对比，需要重载大于号。如果a.dist>b.dist，则表示
// a>b,因为是小顶堆，所以b在前，即dist越小越靠前
bool operator>(const Node &a, const Node &b) {
    return a.dist > b.dist;
}

priority_queue, greater> q;
//邻接表
int idx, h[N], e[M], w[M], ne[M];
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
//迪杰斯特拉
int dijkstra() {
    memset(d, 0x3f, sizeof d);    //初始化距离
    memset(cnt, 0, sizeof cnt);   //记录最短边个数，次短边个数
    memset(st, false, sizeof st); //没有在队列中
    d[S][0] = 0;                  //起点最短路长度为0，起点次长路径不存在，为INF
    cnt[S][0] = 1;                //起点最短路个数为1，起点次长路径不存在，为INF

    //距离，节点号，类型:相对于拆点，一分为二
    q.push({d[S][0], S, 0});
    while (q.size()) {
        auto t = q.top();
        q.pop();
        // u:节点号 type:类型(最短，次短)
        int u = t.id, type = t.type;
        //二维状态描述是不是已经入过队了
        if (st[u][type]) continue;

        //入队
        st[u][type] = true;
        for (int i = h[u]; ~i; i = ne[i]) {
            int j = e[i];
            int dist = d[u][type] + w[i]; //可以用来松驰的可能距离

            //这里将“比最短路长度多1的距离”定义为次短距离
            //与正常含义的次短距离不同，需要注意区分，否则理解不了

            //小于最短距离
            if (dist < d[j][0]) {
                //如果最短距离可以变为次短距离
                if (dist + 1 == d[j][0]) {
                    d[j][1] = d[j][0];       //用最短距离更新次短距离
                    cnt[j][1] = cnt[j][0];   //最短距离数量更新次短距离数量
                    q.push({d[j][1], j, 1}); //次短距离入队列
                }
                d[j][0] = dist;          //更新最短距离
                cnt[j][0] = cnt[u][0];   //更新最短距离的数量
                q.push({d[j][0], j, 0}); //最短距离入队列
            }
            //等于最短距离
            else if (dist == d[j][0])
                cnt[j][0] += cnt[u][0]; //最短距离数累加
            //等于次短距离
            else if (dist == d[j][0] + 1) {
                if (!cnt[j][1]) {            //没有记录过次短距离
                    d[j][1] = dist;          //记录上
                    q.push({d[j][1], j, 1}); //次短距离入队列
                }
                //这里一定要写成type，因为type是0或者1都可能触发该分支
                cnt[j][1] += cnt[u][type];
            }
        }
    }
    //返回终点最短距离和次短距离的和
    return cnt[F][0] + cnt[F][1];
}
int main() {
    int T;
    // T组测试数据
    cin >> T;
    while (T--) {
        //多组测试数据，需要初始化
        memset(h, -1, sizeof h);
        idx = 0;
        // n个节点，m条边
        cin >> n >> m;
        int a, b, c;
        while (m--) {
            cin >> a >> b >> c;
            add(a, b, c);
        }

        cin >> S >> F;
        printf("%d\n", dijkstra());
    }
    return 0;
}