观光

AcWing-383-观光

实现

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

const int N = 1010, M = 100010;
struct edge {
    int to, next, w;
};
edge e[M];
int idx, head[N];
struct node {
    int idx, dis, type;
    bool operator < (const node& o) const {
        return dis > o.dis;
    }
};
int n, m, S, F;
int dis[N][2], cnt[N][2];
bool mark[N][2];

void add_edge (int u, int v, int w) {
    e[idx].w = w;
    e[idx].to = v;
    e[idx].next = head[u];
    head[u] = idx ++;
}
int dijkstra () {
    memset(mark, 0, sizeof(mark));
    memset(dis, 0x3f, sizeof(dis));

    priority_queue<node> pq;
    dis[S][0] = 0, cnt[S][0] = 1;
    pq.push({ S, 0, 0 });
    while (!pq.empty()) {
        node cur = pq.top();
        pq.pop();
        if (mark[cur.idx][cur.type] == true) continue;
        mark[cur.idx][cur.type] = true;
        for (int i = head[cur.idx]; i != -1; i = e[i].next) {
            int to = e[i].to, w = e[i].w;

            if (dis[cur.idx][cur.type] + w < dis[to][0]) {
                dis[to][1] = dis[to][0];
                cnt[to][1] = cnt[to][0];
                pq.push({ to, dis[to][1], 1 });

                dis[to][0] = dis[cur.idx][cur.type] + w;
                cnt[to][0] = cnt[cur.idx][cur.type];
                pq.push({ to, dis[to][0], 0 });
            } else if (dis[cur.idx][cur.type] + w == dis[to][0]) {
                cnt[to][0] += cnt[cur.idx][cur.type];
            } else if (dis[cur.idx][cur.type] + w < dis[to][1]) {
                dis[to][1] = dis[cur.idx][cur.type] + w;
                cnt[to][1] = cnt[cur.idx][cur.type];
                pq.push({ to, dis[to][1], 1 });
            } else if (dis[cur.idx][cur.type] + w == dis[to][1]) {
                cnt[to][1] += cnt[cur.idx][cur.type];
            }
        }
    }

    int res = cnt[F][0];
    if (dis[F][1] == dis[F][0] + 1) res += cnt[F][1];
    return res;
}

int main () {
    int T;
    cin >> T;
    while (T --) {
        idx = 0;
        memset(head, -1, sizeof(head));

        cin >> n >> m;
        for (int i = 1, u, v, w; i <= m; ++ i) {
            cin >> u >> v >> w;
            add_edge(u, v, w);
        }
        cin >> S >> F;

        cout << dijkstra() << endl;
    }
    return 0;
}