洛谷P 1608経路統計【膜改dij】

転送ドア//題意:1-nの最短ルート数を求める.
注意の1つは重辺が1本しかないので(だから私は2発waしました)、私たちは図を建てるときに重さを払う必要があります.
そして、この点までの最短ルートが何本あるかを記録する配列を開くので、dis[to]==dis[u.to]+e[i].w; このレコード配列を更新するには、ans[to]+=ans[u.to];元のdijでいくつかの小さな変化を行えばよい.AC Code

const int maxn = 2e3+5;
int cas=1;
struct node {
    int to, next, w;
    bool operator return w > a.w;
    }
}e[maxn*maxn];
int cnt, head[maxn];
void add(int u, int v, int w) {
    e[cnt] = node{v, head[u], w};
    head[u] = cnt++;
}
void init() {
    cnt = 0;
    Fill(head, -1);
}
int dis[maxn], vis[maxn];
int ans[maxn];
void dij(int st, int ed) {
    priority_queueq;
    q.push(node{st, 0, 0});
    Fill(dis, inf); Fill(vis, 0); Fill(ans ,0);
    dis[st] = 0; ans[st] = 1;
    while(!q.empty()) {
        node u = q.top();
        q.pop();

        if (vis[u.to]) continue;
        vis[u.to] = 1;

        for (int i = head[u.to] ; ~i ; i = e[i].next) {
            int to = e[i].to;
            int d = u.w + e[i].w;
           // cout << "BBB" <<  u.to << ' ' << to << ' ' << dis[to] << ' ' << d << ' ' << endl;
            if (d < dis[to]) {
                dis[to] = d;
                ans[to] = ans[u.to];
                q.push(node{to, 0, d});
            }
            else if (d == dis[to]) ans[to] += ans[u.to];
           // cout << "AAA" << ans[u.to] << ' ' << ans[to] << endl;
        }
    }
    if (dis[ed] == inf) cout << "No answer" << endl;
    else printf("%d %d
", dis[ed], ans[ed]);
}
int s[maxn][maxn];
void solve()
{
    int n, m;
    scanf("%d%d",&n, &m);
    init();
    for (int i = 1 ; i <= m ; i ++) {
        int u, v, w;
        scanf("%d%d%d ", &u, &v, &w);
        if (s[u][v] == w) continue;  //   
        s[u][v] = w;
        add(u, v, w);
    }
    dij(1, n);
}